% !TeX spellcheck = de_DE
\documentclass[UTF8,a4paper]{book} %设为A4纸
\usepackage{geometry}
\geometry{left=2cm,right=3cm,top=4cm,bottom=3cm} %设置页边距
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{verbatim}  %use verbatim
\usepackage{ctex}
\usepackage{ifthen}
\usepackage{makeidx}

\usepackage{extarrows} %use \xlongrightarrow
\usepackage{arydshln} %为了在array中使用：表示虚线

\usepackage{xcolor}
\colorlet{lightcyan}{cyan!40!white}
\usepackage{graphicx}
%\usepackage{chngcntr}
\usepackage{stackengine}

\usepackage{tasks}

\newlength{\longestlabel}

\settowidth{\longestlabel}{\bfseries viii.}

\usepackage[lastexercise]{exercise}
%\counterwithin{Exercise}{chapter}
%\counterwithin{Answer}{chapter}

%\renewcounter{Exercise}[chapter]

\setlength{\QuestionIndent}{7em}

\usepackage{enumerate}

\newboolean{printanswer}

%---------------------答案格式开始定义-----------------------------------------
%判断题后面加括号
\newcommand{\pd}[2][1]{\nolinebreak\dotfill\mbox{\raisebox{-1.8pt}
		{$\cdots$}(\makebox[#1 cm][c]{
			\ifthenelse{\boolean{printanswer}}
			{\ifthenelse{\equal{#2}{t}}{\Checkmark}{\XSolid}}
			{}
		})}}


%填空题画线  \tk
%\newcommand{\tk}[2][2.5]{\; \underline{\hspace{#1 cm} \hphantom{#2} \hspace{#1 cm} } \, }
\usepackage{ulem}
\newcommand{\tk}[2][0.5]{\;\uline{ 
		\hspace*{#1 cm}
		\ifthenelse{\boolean{printanswer}}{#2}{\hphantom{#2}}  
		\hspace*{#1 cm}
} }
%简答题  \jd
\newcommand{\jd}[2][4]{\par
	%\begin{minipage}[t][#1cm][t]{0.92\linewidth}	
		\ifthenelse{\boolean{printanswer}}{
			\begin{Answer}
				答：\par
				#2
			\end{Answer}
		}
		{}  
	%\end{minipage} 
}	
%---------------------------答案格式结束定义---------------------------------
\usepackage[breaklinks,colorlinks,linkcolor=black,citecolor=black,urlcolor=black]{hyperref} %生成pdf中的书签
\setboolean{printanswer}{false} %控制是否输出习题的答案

\begin{document}
	
\ifthenelse{\boolean{printanswer}}{
	\title{《现代密码学》习题集(有答案)}
}
{
	\title{《现代密码学》习题集(无答案)}
}


\maketitle

\tableofcontents
	
\chapter{基本概念}
	\begin{Exercise}
		密码学中，把没有加密的消息和加密后的消息分别称为什么？英文单词是什么？
	\end{Exercise}
	\jd{
		密文 cipher text和明文plain text
	}

	\begin{Exercise}
		基本安全属性有哪些？
	\end{Exercise}
	\jd{
		安全属性，有时也称为安全目标，通常认为包括：
		\begin{enumerate}
			\item 机密性\textbf{Confidentiality}
			\item 完整性\textbf{Integrity}
			\item 非否认\textbf{Non-repudiation}
			\item 可认证\textbf{Authentication}
			\item 访问控制\textbf{Access Control}
		\end{enumerate}

	}

	\begin{Exercise}
	 给出被动攻击和主动攻击的定义，列出并简单定义各类攻击。\cite{mooc现代密码学聂旭云}
	\end{Exercise}
   	\jd{
   		\begin{itemize}
   			\item 被动攻击，对系统的保密性进行攻击，如通过搭线窃听等，对文件或者程序的非负复制，以获得他人的信息。通常分为两类。
   			\begin{itemize}
   				\item 获取消息内容。
   				\item 进行业务流分析。
   			\end{itemize}
  				\item 主动攻击包括对数据流的篡改或产生某些假的数据流。主动攻击主要分为三类。
  				\begin{itemize}
  					\item 中断。
  					\item 篡改
  					\item 伪造
  				\end{itemize}
   		\end{itemize}
   	}
	  	
	\begin{Exercise}
		对抗被动攻击和主动攻击的一般性原则。
	\end{Exercise}
	\jd{
		被动攻击很难检测，所以对抗的重点是防范，而非检测。主动攻击想绝对防止很困难，对抗的主要方法是检测和恢复。
	}

   	\begin{Exercise}
   		柯克霍夫斯原则是什么？
   	\end{Exercise}
   	\jd{
   		柯克霍夫斯在其1883年出版的《军事密码学》一书中，提出“密码系统的安全性应该仅仅取决于所使用的密钥的机密性，而不是对该方案本身的保密”，这就是现在被大家广泛接受的“柯克霍夫斯原则”。
   	}
   	
   	\begin{Exercise}
   		什么是完全保密（perfect security）？
   	\end{Exercise}
   	\jd{
   		完全保密系统，通俗来讲，就是当我们获得密文后，对于我们了解明文，没有任何帮助。换句话说，消息M的概率为$P(M)$,在知道密文E的情况下，消息M的概率为$P_E(M)$，一个完全保密系统就是说对于所有可能的E和M，有$P(M)=P_E(M)$。
   	}
   
   	\begin{Exercise}
   		什么是一次一密？
   	\end{Exercise}
   	\jd{一次一密的重要特征是其密钥是一个随机序列，密钥只使用一次，且密钥的长度等
   		于明文序列的长度。一次一密理论上不可攻破的密码系统。也就是说一次一密系统是一
   		种完全保密系统，或者说是完全保密系统的一类实现。}
   	
   	\begin{Exercise}
   		密码攻击根据攻击者掌握的信息可以分为哪几种类型，并对每种类型做简单解释。
   	\end{Exercise}
   	\jd{
   		\begin{enumerate}
   			\item 密码分析员掌握除了密钥外，密码系统的加密和解密算法.
   			\item 仅知密文攻击(ciphertext-only attack)，密码分析员能够获得密文。.
   			\item 已知明文攻击(known-plaintext attack)，密码分析员能够获得某些明文和这些明文对应的密文.
   			\item 选择明文攻击(chosen-plaintext attack)，密码分析员能够有选择地获得明文和这些明文对应的密文.
   			\item 选择密文攻击(chosen-ciphertext attack)，密码分析员可以像合法用户那样发送加密的信息.
   			\item 密码分析员可以改变、截取或重新发送信息。
   		\end{enumerate}	
   }

   	\begin{Exercise}
   		简述密码体制的基本定义。
   	\end{Exercise}
   	\jd{
   		一个密码体制是指这样一种数学映射：
   		\begin{enumerate}
   			\item 明文消息空间M，某个字母表上的串集,M表示message。
   			\item 密文消息空间C，可能的密文消息集,C表示cipher。
   			\item 加密密钥空间$K_e$，可能的加密密钥集，K表示key，e表示encrypt。
   			\item 解密密钥空间$K_d$，可能的解密密钥集。d表示decryp。
   			\item 加密算法$E:M\times K_e \rightarrow C$,也可写为$c=E_{k_e}(m)$.
   			\item 加密算法$D:C\times K_d \rightarrow M$,也可写为$m=D_{k_d}(c)$.
   			\item 密码体制满足$D_{k_d}(E_{k_e}(m))=m$.
   		\end{enumerate}
   	}
   
   	\begin{Exercise}
   		什么是对称密码体制和非对称密码体制？
   	\end{Exercise}
   	\jd{
   		对称密码体制是指加密密钥和解密密钥相同的密码体制，反之称为非对称密码体制。
   	}
   
	\begin{Exercise}
	   	什么是计算安全？	   	
	\end{Exercise}
	\jd{
	   	如果破译者在选择最有效的算法前提以下，破解一个密码体制依然需要很大的资源，而这个资源是破译者无法承受的，那么我们称为这个密码体制是计算安全的。在通俗的来讲，就是“如果我们使用最好的算法来破译一个密码体制至少需
	   	要 n 次操作，而 n 是一个非常大的数，则我们称这个密码体制是计算上安全的"。
	}
	
	\begin{Exercise}
		密码学的两个分支是什么？	   	
	\end{Exercise}
	\jd{
		密码编码学和密码分析学
	}

\chapter{古典密码}
	\begin{Exercise}
		利用Caesar密码对nice进行加密，产生的密文是什么？\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		Caesar密码变换表如下所示：\par
		\begin{center}
			\begin{tabular}{|c|c||c|c|}
				\hline 
				明文& 密文 & 明文 & 密文 \\ 
				\hline 
				a& d & n & q \\ 
				\hline 
				b& e & o & r \\ 
				\hline 
				c& f & p & s \\ 
				\hline 
				d& g & q & t \\ 
				\hline 
				e& h & r & u \\ 
				\hline 
				f& i & s & v \\ 
				\hline 
				g& j & t & w \\ 
				\hline 
				h& k & u & x \\ 
				\hline 
				i& l & v & y \\ 
				\hline 
				j& m & w & z \\ 
				\hline 
				k& n & x & a \\ 
				\hline 
				l& o & y & b \\ 
				\hline 
				m& p & z & c \\ 
				\hline 
			\end{tabular} 
		\end{center}
		\par
		查表可得加密后的密文为：
		\textbf{qlfh}
	}

	\begin{Exercise}
		加法密码和Caesar密码之间的关系。
	\end{Exercise}
	\jd{Caesar是加法密码$k=3$的时的特例。}
	
	\begin{Exercise}
		设乘法密码的加密函数为$c=11m \pmod{26}$，则其解密密钥是多少？
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		$(11)^{-1} \pmod{26}=19 \pmod{26}$\par
		故此乘法密码的解密函数为：$m=19c \pmod{26}$\\
		\textbf{注：}\\
		1.验证：$11\times 19=209=26\times 8+1$\\
		2.求乘法逆元的算法之一：扩展欧几里得算法。
	}

	\begin{Exercise}
		仿射密码通用加密函数为$c=am+b \pmod{26}$,m为明文，c为密文，通常，我们把仿射密码体制中的什么看做此体制的密钥？\cite{mooc现代密码学聂旭云} 设想您采用了仿射加密，那么在相互传输消息时需要先把密钥告诉对方，假设密钥的交换采用文件方式，并且文件是通过安全信道传输，试想想有几种具体实现的方案，并实现验证。\\
		\textbf{提示:}\\
		1、可以直接将两个变量以二进制的方式写入文件，在使用时，依次读出。\\
		2、可以定义一个结构体，然后将此结构体直接写入文件，在使用时读出此结构体。\\
		3、如果是windows系统，可以使用windows的API WritePrivateProfileString和GetPrivateProfileString，具体可参考微软网站上的示例代码\url{https://docs.microsoft.com/en-us/windows/win32/api/winbase/nf-winbase-writeprivateprofilestringa}.当然，你也可以自定义函数，来实现WritePrivateProfileString和GetPrivateProfileString功能，以此来提高你程序的可移植性。Linux下有ini文件操作库，所以你可以定义一个接口库(一个函数壳)，根据不同的编译参数，决定链接windows库还是linux库，同样也可以提高程序的可移植性。
	\end{Exercise}
	\jd{我们把仿射密码体制中的a,b看成密钥。}
	
	\begin{Exercise}
		仿射密码加密函数为$c=17m+2 \pmod{26}$，求其解密函数？
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		$(17)^{-1} \pmod{26} = 23 \pmod{26}$\par
		解密函数为：$m=23(c-2) \pmod{26} \Rightarrow m=23c+6 \pmod{26}$
		\\
		\textbf{注：}\\
		1.验证：$17\times 23=391=26\times 15+1$\\
		2.验证：$23 \times 2=46=26+20,m=23c-20 \pmod{26}\rightarrow m=23c-20+26 \pmod{26} \rightarrow m=23c+6 \pmod{26}$\\
		3.求乘法逆元的算法之一：扩展欧几里得算法。
	}

	

	\begin{Exercise}
		已知敌手在用模26下的仿射密码加密，获取的密文为：gzyyf\\
		已知明文是"he"开头，请破解此消息。\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		26个字母分别和$0,1,2,\ldots$对应，h对应7，e对4，g对6，z对25，有：\\
		$ 
		\begin{matrix}
			6=7a+b \pmod{26}\\
			25=4a+b \pmod{26}
		\end{matrix}
		$\\
		
		解得$a=11,b=7$，$a^{-1} \pmod {26}=19$，解密方程为$a^{-1} \left( x-b \right) \pmod {26}$，依次可求得yyf对应得明文为llo，故完整明文为：hello	
	}

	\begin{Exercise}
		设仿射变换得加密是$E_{11,23}\left( m \right) ==11m+23 \pmod{26}$,对明文"the national security agency"加密，并用解密变换$D_{11,23}\left( c \right) ==11^{-1}\left( c-23\right)  \pmod{26}$进行解密验证。\cite{yang-mcry}
	\end{Exercise}
	\jd{
	①明文m=THE NATIONAL SECURITY AGENCY用数字表示为：
	m=[19  7  4  13  0  19  8  14  13  0  11  18  4  2  20  17  8  19  24  0  6  4  13  2  24 ]
	根据${{E}_{11,23}}(m)\equiv 11m+23(\bmod 26)$，对明文中的每一个字符计算出相应的密文字符
	c=[24  22  15  10  23  24  7  21  10  23  14  13  15  19  9  2  7  24  1  23  11  15  10  19  1 ]
	由此得到密文c=YWPKXYHVKXONPTJCHYBXLPKTB
	②使用解密变换验证加密结果过程如下：
	由11*19≡1 (mod 26)知$11^{-1}=19$
	(注：求模逆元可以通过欧几里得算法或者直接穷举1~25)
	根据$D_{11,23}(c)≡19* (c-23) (mod 26)$，对密文中的每一个字符计算出相应的明文字符
	m=[19  7  4  13  0  19  8  14  13  0  11  18  4  2  20  17  8  19  24  0  6  4  13  2  24 ]
	由此得到m=THE NATIONAL SECURITY AGENCY，解密结果与明文一致，正确。
	
	}

	\begin{Exercise}
		设由仿射变换对一个明文加密得到的密文为：edsgickxhuklzveqzvkxwkzzukvcuh。又已知明文的前两个字符为“if”，对该明文解密。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设加密变换为c=Ea,b(m)≡a*m+b(mod 26)
		由题目可知，明文前两个字符为if，相应密文为ed，即有：
		E(i)=e，4≡a*8+b(mod 26) ，(i=8，e=4)，
		E(f)=d，3≡a*5+b(mod 26) ，(f=5，d=3)，
		由上述两式可求得，a=9，b=10
		因此解密变换为D9,10(c)≡9-1*(c-10) (mod 26)
		又由3*9≡1 (mod 26)可知9-1=3
		密文对应的数字表示为：
		c=[4  3  18  6  8  2  10  23  7  20  10  11  25  21  4  16  25  21  10  23  22  10  25  20  10  21  2  20  7 ]
		根据D9,10(c)≡9-1*(c-10) (mod 26)≡3*(c-10) (mod 26)，对密文中的每一个字符计算出相应的明文字符
		c=[8  5  24  14  20  2  0  13  17  4  0  3  19  7  8  18  19  7  0  13  10  0  19  4  0  7  2  4  17 ]
		由此得到明文m=ifyoucanreadthisthankateahcer
	}

	\begin{Exercise}
		一个多表替代的加密函数为:\\
		\begin{equation}
		\left( \begin{matrix}
		y_1\\
		y_2
		\end{matrix}\right) =\left( \begin{matrix}
		11&2\\
		5&23
		\end{matrix}\right) \left( \begin{matrix}
		x_1\\
		x_2
		\end{matrix}\right) \pmod {26}
		\end{equation}
		其中$\left( y_1,y_2\right) $为密文，$\left( x_1,x_2 \right) $为明文，计算该加密函数对应的解密函数。\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		\begin{equation}
		\left( \begin{matrix}
		11&2\\
		5&23
		\end{matrix}\right)^{-1}  \pmod {26} =
		\left( \begin{matrix}
		17&20\\
		11&7
		\end{matrix}\right)
		\end{equation}
	}

	\begin{Exercise}
		设多表代换密码中
		$A=\left( \begin{matrix}
		3 & 13 & 21 & 9  \\
		15 & 10 & 6 & 25  \\
		10 & 17 & 4 & 8  \\
		1 & 23 & 7 & 2  \\
		\end{matrix} \right),B=\left( \begin{matrix}
		1  \\
		21  \\
		8  \\
		17  \\
		\end{matrix} \right)$
		加密为：${{C}_{i}}\equiv A{{M}_{i}}+B(\bmod 26)$,对明文“PLEASE SEND ME THE BOOK,MY CREDIT CARD NO IS SIX ONE TWO ONE THREE EIGHT SIX ZERO ONE SIX EIGHT FOUR NINE SEVEN ZERO TWO”用解密变换 :${{M}_{i}}\equiv {{A}^{-1}}+B{{(\bmod 26)}_{{}}}$验证你的结果，其中${{A}^{-1}}=\left( \begin{matrix}
		23 & 13 & 20 & 5  \\
		0 & 10 & 11 & 0  \\
		9 & 11 & 15 & 22  \\
		9 & 22 & 6 & 25  \\
		\end{matrix} \right)$
		.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		加密时，先将明文分组，每四个一组：\\
		$
		{{M}_{1}}\equiv 
		\left[ 
			\begin{matrix}
				15  \\
				11  \\
				4  \\
				0  \\
			\end{matrix} 
		\right]
		{{M}_{2}}\equiv 
		\left( \begin{matrix}
					18  \\
					4  \\
					18  \\
					4  \\
				\end{matrix} 
		\right){{M}_{3}}\equiv 
		\left( \begin{matrix}
					13  \\
					3  \\
					12  \\
					4  \\
				\end{matrix} 
		\right){{M}_{4}}\equiv 
		\left( \begin{matrix}
					19  \\
					7  \\
					4  \\
					1  \\
				\end{matrix} 
		\right){{M}_{5}}\equiv 
		\left( \begin{matrix}
					14  \\
					14  \\
					10  \\
					12  \\
				\end{matrix} 
		\right){{M}_{6}}\equiv 
		\left( \begin{matrix}
					24  \\
					2  \\
					17  \\
					4  \\
				\end{matrix} 
		\right) \\ 
		{{M}_{7}}\equiv 
		\left( \begin{matrix}
					3  \\
					8  \\
					19  \\
					2  \\
				\end{matrix} 
		\right){{M}_{8}}\equiv 
		\left( \begin{matrix}
					0  \\
					17  \\
					3  \\
					13  \\
				\end{matrix} 
		\right){{M}_{9}}\equiv 
		\left( \begin{matrix}
					14  \\
					8  \\
					18  \\
					18  \\
				\end{matrix} 
		\right){{M}_{10}}\equiv 
		\left( \begin{matrix}
					8  \\
					23  \\
					14  \\
					13  \\
				\end{matrix} 
		\right){{M}_{11}}\equiv 
		\left( \begin{matrix}
					4  \\
					19  \\
					22  \\
					14  \\
				\end{matrix} 
		\right){{M}_{12}}\equiv 
		\left( \begin{matrix}
					14  \\
					13  \\
					4  \\
					19  \\
				\end{matrix} 
		\right) \\ 
		{{M}_{13}}\equiv 
		\left( \begin{matrix}
					7  \\
					17  \\
					4  \\
					4  \\
				\end{matrix} 
		\right){{M}_{14}}\equiv 
		\left( \begin{matrix}
					4  \\
					8  \\
					6  \\
					7  \\
				\end{matrix} 
		\right){{M}_{15}}\equiv 
		\left( \begin{matrix}
					19  \\
					18  \\
					8  \\
					23  \\
				\end{matrix} 
		\right){{M}_{16}}\equiv 
		\left( \begin{matrix}
					25  \\
					4  \\
					17  \\
					4  \\
				\end{matrix} 
		\right){{M}_{17}}\equiv 
		\left( \begin{matrix}
					14  \\
					13  \\
					4  \\
					18  \\
				\end{matrix} 
		\right){{M}_{18}}\equiv 
		\left( \begin{matrix}
					8  \\
					23  \\
					4  \\
					8  \\
				\end{matrix} 
		\right) \\ 
		{{M}_{19}}\equiv 
		\left( \begin{matrix}
					6  \\
					7  \\
					19  \\
					5  \\
				\end{matrix} 
		\right){{M}_{20}}\equiv 
		\left( \begin{matrix}
					14  \\
					20  \\
					17  \\
					13  \\
				\end{matrix} 
		\right){{M}_{21}}\equiv 
		\left( \begin{matrix}
					8  \\
					13  \\
					4  \\
					18  \\
				\end{matrix} 
		\right){{M}_{22}}\equiv 
		\left( \begin{matrix}
					4  \\
					21  \\
					4  \\
					13  \\
				\end{matrix} 
		\right){{M}_{23}}\equiv 
		\left( \begin{matrix}
					25  \\
					4  \\
					17  \\
					14  \\
				\end{matrix} 
		\right){{M}_{24}}\equiv 
		\left( \begin{matrix}
					19  \\
					22  \\
					14  \\
					{}  \\
				\end{matrix} 
		\right) 
		$
		再代入加密变换：${{C}_{i}}\equiv A{{M}_{i}}+B(\bmod 26)$,得到计算结果：\\
		
		$
		{{C}_{1}}\equiv \left( \begin{matrix}
		13  \\
		16  \\
		23  \\
		1  \\
		\end{matrix} \right){{C}_{2}}\equiv \left( \begin{matrix}
		1  \\
		19  \\
		22  \\
		1  \\
		\end{matrix} \right){{C}_{3}}\equiv \left( \begin{matrix}
		3  \\
		2  \\
		9  \\
		9  \\
		\end{matrix} \right){{C}_{4}}\equiv \left( \begin{matrix}
		8  \\
		9  \\
		3  \\
		19  \\
		\end{matrix} \right){{C}_{5}}\equiv \left( \begin{matrix}
		23  \\
		3  \\
		2  \\
		5  \\
		\end{matrix} \right){{C}_{6}}\equiv \left( \begin{matrix}
		24  \\
		5  \\
		18  \\
		6  \\
		\end{matrix} \right) \\ 
		{{C}_{7}}\equiv \left( \begin{matrix}
		11  \\
		24  \\
		6  \\
		3  \\
		\end{matrix} \right){{C}_{8}}\equiv \left( \begin{matrix}
		12  \\
		14  \\
		23  \\
		13  \\
		\end{matrix} \right){{C}_{9}}\equiv \left( \begin{matrix}
		11  \\
		11  \\
		6  \\
		13  \\
		\end{matrix} \right){{C}_{10}}\equiv \left( \begin{matrix}
		7  \\
		0  \\
		15  \\
		2  \\
		\end{matrix} \right){{C}_{11}}\equiv \left( \begin{matrix}
		16  \\
		25  \\
		25  \\
		16  \\
		\end{matrix} \right){{C}_{12}}\equiv \left( \begin{matrix}
		25  \\
		2  \\
		17  \\
		6  \\
		\end{matrix} \right) \\ 
		{{C}_{13}}\equiv \left( \begin{matrix}
		25  \\
		4  \\
		25  \\
		9  \\
		\end{matrix} \right){{C}_{14}}\equiv \left( \begin{matrix}
		20  \\
		8  \\
		4  \\
		1  \\
		\end{matrix} \right){{C}_{15}}\equiv \left( \begin{matrix}
		17  \\
		17  \\
		18  \\
		16  \\
		\end{matrix} \right){{C}_{16}}\equiv \left( \begin{matrix}
		13  \\
		4  \\
		12  \\
		21  \\
		\end{matrix} \right){{C}_{17}}\equiv \left( \begin{matrix}
		16  \\
		3  \\
		9  \\
		4  \\
		\end{matrix} \right){{C}_{18}}\equiv \left( \begin{matrix}
		12  \\
		23  \\
		13  \\
		0  \\
		\end{matrix} \right) \\ 
		{{C}_{19}}\equiv \left( \begin{matrix}
		8  \\
		4  \\
		17  \\
		15  \\
		\end{matrix} \right){{C}_{20}}\equiv \left( \begin{matrix}
		23  \\
		0  \\
		10  \\
		12  \\
		\end{matrix} \right){{C}_{21}}\equiv \left( \begin{matrix}
		24  \\
		17  \\
		1  \\
		24  \\
		\end{matrix} \right){{C}_{22}}\equiv \left( \begin{matrix}
		19  \\
		16  \\
		5  \\
		12  \\
		\end{matrix} \right){{C}_{23}}\equiv \left( \begin{matrix}
		13  \\
		4  \\
		12  \\
		21  \\
		\end{matrix} \right){{C}_{24}}\equiv \left( \begin{matrix}
		14  \\
		12  \\
		4  \\
		{}  \\
		\end{matrix} \right) \\ 
		$

		知密文为：NQXB  BTWB  DCJJ  IJDT  XDCF  YFSG \\
		LYGD  MOXN  LLGN  HAPC  QZZQ  ZCRG\\
		ZEZJ  UIEB  RRSQ  NEMV  QDJE  MXNA\\
		IERP  XAKM  YRBY  TQFM  NEMV  OME \\
		同上，解密时，先将密文分组，再代入解密变换：${{M}_{i}}\equiv {{A}^{-1}}+B{{(\bmod 26)}_{{}}}$\\
		得到明文：PLEA  SESE  NDME  THEB  OOKM  YCRE \\
		DITC  ARDN  OISS  IXON  ETWO  ONET\\
		HREE  EIGH  TSIX  ZERO  ONES   IXEI \\
		GHTF  OURN  INES  EVEN  ZERO  TWO\\
		解密验证结果与明文相符。
		
	}
	\begin{Exercise}
		设多表代换密码 ${{C}_{i}}\equiv A{{M}_{i}}+B(\bmod 26)$ 中，A是2×2矩阵，B是零矩阵，又知明文“dont”被加密为“elni”，求矩阵A。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设矩阵 $A\equiv \left( \begin{matrix}
		\text{a} & b  \\
		c & d  \\
		\end{matrix} \right)$
		
		由m=dont=(3,14,13,19)，c=elni=(4,11,13,8)可知:
		$\left( \begin{matrix}
		4  \\
		11  \\
		\end{matrix} \right)\equiv \left( \begin{matrix}
		\text{a} & b  \\
		c & d  \\
		\end{matrix} \right)\left( \begin{matrix}
		3  \\
		14  \\
		\end{matrix} \right)\text{(mod}26)$
		\\
		$\left( \begin{matrix}
		13  \\
		8  \\
		\end{matrix} \right)\equiv \left( \begin{matrix}
		\text{a} & b  \\
		c & d  \\
		\end{matrix} \right)\left( \begin{matrix}
		13  \\
		9  \\
		\end{matrix} \right)\text{(mod}26)$
		\\
	
		解得： $A\equiv \left( \begin{matrix}
		10 & 13  \\
		9 & 23  \\
		\end{matrix} \right)$	
	}


\chapter{流密码}
	\begin{Exercise}
		流密码是属于哪种密码体制？
	\end{Exercise}
	\jd{流密码是对称密码体制。}
	
	\begin{Exercise}
		简述Golomb的随机性公设。
	\end{Exercise}
	\jd{
		Golomb 提出了伪随机周期序列应该满足 3 个随机性公设：\par
		1. 在序列的一个周期内，0 与 1 的个数相差最多为 1.\par
		2. 在序列的一个周期内，长为 1 的游程占游程总数的$\dfrac{1}{2}$ ，长为 2 的游程占游程总数的$\dfrac{1}{2^2}$, 长为 i 的游程占游程总数的$\dfrac{1}{2^i}$，且在等长的游程中 0 的游程个数与 1的游程个数相等。\par
		3. 异自相关函数是一个常数。
	}
	
	\begin{Exercise}
		在序列密码中，分别有哪两种加密方式？
	\end{Exercise}
	\jd{在序列密码中有同步加密方式和自同步加密方式}
	
	\begin{Exercise}
		序列密码设计的核心问题是什么？
	\end{Exercise}
	\jd{序列密码设计的核心问题是密钥序列发生器的设计。}
	
	\begin{Exercise}
		设一个3级线性反馈移位寄存器(LFSR)的特征多项式为$f(x)=1+x^2+x^3$.\\
		(1)画出该LFSR的框图。\\
		(2)给出序列的递推关系式。\\
		(3)设初始状态$(a_0,a_1,a_2)=(0,0,1)$,写出输出序列级序列及周期。\\
		(4)列出序列的游程。
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		(1)LFSR的框图如\ref{fig:lfsr}所示。
		\par
		(2)输出序列的递推关系为：$a_n = a_{n-2} + a_{n-3}\quad n=3,4,5,\ldots$
		\par
		(3)初始状态为$(a_0,a_1,a_2)=(0,0,1)$，输出序列为：
		\[\underline{0010111} 0010111  \ldots  \]
		周期为7.
		\par
		(4)0的1游程，1个；1的1 游程，1个；0的2游程1个；1的3游程1个。
	}

	\begin{figure}[h]
		\centering
		\includegraphics[width=0.6\linewidth] {ex2-1.png}
		\caption{LFSR框图}
		\label{fig:lfsr}
	\end{figure}

	\begin{Exercise}
		(1)已知流密码的密文串$1010110110$，相应的明文串$0100010001$，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破解该密码系统。\cite{mooc现代密码学聂旭云}\par
		(2)现在我们获得了后续的密文串$111000111000$，请问明文是什么？
	\end{Exercise}
	\jd{
	(1)首先计算密钥串：\\
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
			\hline 
			明文 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 
			\hline 
			密文 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 
			\hline 
			密钥 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 
			\hline 
		\end{tabular}  \par
		密钥流为：1110100111.\par
		3级移位寄存器通式：
		\[
		\left\lbrace \begin{matrix}
			a_3 = c_1 a_2 \oplus c_2 a_1 \oplus c_3 a_0\\
			a_4 = c_1 a_3 \oplus c_2 a_2 \oplus c_3 a_1\\
			a_5 = c_1 a_4 \oplus c_2 a_3 \oplus c_3 a_2\\
		\end{matrix}
		\right.
		\]
		用已知的明文和密文对应关系，可以得：
		\[
		\left\lbrace \begin{matrix}
		0 = c_1  \oplus c_2  \oplus c_3 \\
		1 = c_2  \oplus c_3 \\
		0 = c_1  \oplus c_3 \\
		\end{matrix}
		\right.
		\]
		写成矩阵形式：
		\[\begin{bmatrix}0&1&0 \end{bmatrix}=\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}
		\begin{bmatrix}
		1 & 0 & 1\\
		1 & 1 & 0 \\
		1 & 1 & 1 \\
		\end{bmatrix}
		\]
		利用Gauss-Jordan算法求逆矩阵：\\
		$\left[ \begin{array}{ccc:ccc}
		1 & 0 & 1 &   1 & 0 & 0 \\
		1 & 1 & 0 &   0 & 1 & 0 \\
		1 & 1 & 1 &   0 & 0 & 1 \\
		\end{array}	\right] \xlongrightarrow{\substack{R_1+R_2 \\ R_1+R_3}}
		\left[ \begin{array}{ccc:ccc}
		1 & 0 & 1 &   1 & 0 & 0 \\
		0 & 1 & 1 &   1 & 1 & 0 \\
		0 & 1 & 0 &   1 & 0 & 1 \\
		\end{array}	\right] \xlongrightarrow{\substack{R_2+R_3}}
		\left[ \begin{array}{ccc:ccc}
		1 & 0 & 1 &   1 & 0 & 0 \\
		0 & 1 & 1 &   1 & 1 & 0 \\
		0 & 0 & 1 &   0 & 1 & 1 \\
		\end{array}	\right]  \xlongrightarrow{\substack{R_3+R_1 \\ R_3+R_2}}
		\left[ \begin{array}{ccc:ccc}
		1 & 0 & 0 &   1 & 1 & 1 \\
		0 & 1 & 0 &   1 & 0 & 1 \\
		0 & 0 & 1 &   0 & 1 & 1 \\
		\end{array}	\right]
		$\par
		我们有：\\
		\[\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}=\begin{bmatrix}0&1&0 \end{bmatrix}
		\begin{bmatrix}
		1 & 0 & 1\\
		1 & 1 & 0 \\
		1 & 1 & 1 \\
		\end{bmatrix}^{-1}
		\]
		\[\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}=\begin{bmatrix}0&1&0 \end{bmatrix}
		\begin{bmatrix}
		1 & 1 & 1\\
		1 & 0 & 1 \\
		0 & 1 & 1 \\
		\end{bmatrix}
		\]
		\[\begin{bmatrix}c_1&c_2 &c_3 \end{bmatrix}=\begin{bmatrix}1 & 0 &1 \end{bmatrix}\]
		\par
		解得$c_1=1,c_2=0,c_3=1$。\par
		递推关系为$a_{n-1} = a_n + a_{n-2}$或$a_3 = a_2 +a_0$.
	(2)需要解密的是12bit，前面我们已经获得前序10bit密钥，根据递推关系，我们计算后12bit的密钥：
	$
	a_7=1,a_8=1,a_9=1;\\
	a_{10}=0;\\
	a_{11}=1;\\
	a_{12}=0;\\
	a_{13}=0;\\
	a_{14}=1;\\
	a_{15}=1;\\
	a_{16}=1;\\
	a_{17}=0;\\
	a_{18}=1;\\
	a_{19}=0;\\
	a_{20}=0;\\
	a_{21}=1;\\
	$\par
	计算明文：\par
	\begin{tabular}{ccccccccccccc}
		%\hline 
		密文&  1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0  \\ 
		\hline 
		密钥&  0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 
		\hline 
		明文&  1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 
		%\hline 
	\end{tabular} 
	}

	\begin{Exercise}
		3级线性反馈移位寄存器在 ${{c}_{3}}=1 $时可有4种线性反馈函数，设其初始状态为$\left( {{a}_{1}},{{a}_{2}},{{a}_{3}} \right)=\left( 1,0,1 \right)$ ，求各线性反馈函数的输出序列及周期。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设3级线性反馈特征多项式为$p\left( x \right)=1+{{c}_{1}}x+{{c}_{2}}{{x}^{2}}+{{c}_{3}}{{x}^{3}}$ ，若${{c}_{3}}=1$ 则共有 ${{2}^{2}}=4$种可能的特征多项式,分别为：
		\[{{p}_{1}}\left( x \right)=1+{{x}^{3}}\]
		\[{p}_{2}\left( x \right)=1+x+{x}^{3}\]
		\[{p}_{3}\left( x \right)=1+{{x}^{2}}+{x}^{3}\]
		\[{p}_{4}\left( x \right)=1+x+{{x}^{2}}+{x}^{3}\]
	
		初态$\left( {{a}_{1}},{{a}_{2}},{{a}_{3}} \right)=\left( 1,0,1 \right)$ 。则4种线性反馈函数输出序列分别为：\\
		${{p}_{1}}$输出序列 $a=\overbrace{\underline{101}}\overbrace{101}\underbrace{101}\overbrace{101}\overbrace{101}101\cdots $，周期为3\\
		${p}_{2}$输出序列$a=\overbrace{\underline{101}0011}\overbrace{1010011}\overbrace{1010011}\overbrace{1010011}\overbrace{1010011}10\cdots$, 周期为7，是m序列\\
		${p}_{3}$输出序列 $a=\overbrace{\underline{101}}\overbrace{101}\overbrace{101}\overbrace{101}\overbrace{101}\overbrace{101}\overbrace{101}10\cdots$，周期为3\\
		${p}_{4}$输出序列 $a=\underline{101}0\overbrace{10}\overbrace{10}\overbrace{10}101010101\cdots $，周期为2\\
	}

	\begin{Exercise}
		设n级线性反馈移位寄存器的特征多项式为$p(x)$ ，初始状态为$\left( {{a}_{1}},{{a}_{2}},\cdots ,{{a}_{n-1}},{{a}_{n}} \right)=\left( 00\cdots 01 \right)$ ，证明输出序列的周期等于$p(x)$ 的阶。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		$p(x)$ 的阶定义为 $p\left( x \right)|{{x}^{p}}-1$ 的最小的 p。
		因为初始状态不为零，设r 为序列的最小周期。又因为$p\left( x \right)|{{x}^{p}}-1$ ，所以必存在$q(x)$ ，使得 ${{x}^{p}}-1=p\left( x \right)q\left( x \right)$。\\
		又因为定理2-1有$p\left( x \right)A\left( x \right)=\phi \left( x \right)$ ,
		则  $p\left( x \right)q\left( x \right)A\left( x \right)=\phi \left( x \right)q\left( x \right) \Rightarrow \left( {{x}^{p}}-1 \right)A\left( x \right)=\phi \left( x \right)q\left( x \right)$ ,
		而 q(x)的次数为p-n ，$\phi \left( x \right)$ 的次数不超过 n-1， $\left( {{x}^{p}}-1 \right)A\left( x \right)$的次数不超过 $\left( p-n \right)+\left( n-1 \right)=p-1$。所以 $\forall i$， i是正整数，都有${a}_{i+p}={a}_{i}$ 。
		设$p=kr+t ,{{a}_{i+p}}={{a}_{i+kr+t}}={{a}_{i+t}}={{a}_{i}}\Rightarrow t=0,\Rightarrow r|p $ 。
		即周期为 p(x)的阶，若 p(x)是n次不可约多项式，则序列的最小周期等于 p(x)的阶。
		生成函数 $A\left( x \right)=\frac{\phi \left( x \right)}{p\left( x \right)}$， $p\left( x \right)A\left( x \right)=\phi \left( x \right)\ne 0$， $\phi \left( x \right)$的次数不超过 n-1。
		$
		A\left( x \right)=\sum\limits_{i=1}^{\infty }{{{a}_{i}}}{{x}^{i-1}}=\frac{{{a}_{1}}+{{a}_{2}}x+\cdots +{{a}_{r}}{{x}^{r-1}}}{{{x}^{r}}-1}=\frac{\phi \left( x \right)}{p\left( x \right)}$
		\\
		$
		p\left( x \right)\left( {{a}_{1}}+{{a}_{2}}x+\cdots +{{a}_{r}}{{x}^{r-1}} \right)=\phi \left( x \right)\left( {{x}^{r}}-1 \right)
		$
		
		p(x)不可约，所以$\gcd \left( p\left( x \right),\phi \left( x \right) \right)=1$ ，$p\left( x \right)|\left( {{x}^{r}}-1 \right)$ 。又因为 $m\le r$，所以 r=m。
		
		
	}
	
	\begin{Exercise}
		设 n=4，$f\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)={{a}_{1}}\oplus {{a}_{4}}\oplus 1\oplus {{a}_{2}}{{a}_{3}}$ ，初始状态为$\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)=\left( 1,1,0,1 \right)$ ，求此非线性反馈移位寄存器的输出序列及周期。.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由 $f\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)={{a}_{1}}\oplus {{a}_{4}}\oplus 1\oplus {{a}_{2}}{{a}_{3}}$，初态为 $\left( {{a}_{1}},{{a}_{2}},{{a}_{3}},{{a}_{4}} \right)=\left( 1,1,0,1 \right)$ 。线性递归可得：\\
		$
		{{a}_{5}}=1\oplus 1\oplus 1\oplus 0=1 \\
		{{a}_{6}}=1\oplus 1\oplus 1\oplus 0=1\\
		{{a}_{7}}=0\oplus 1\oplus 1\oplus 1=1\\
		{{a}_{8}}=1\oplus 1\oplus 1\oplus 1=0\\
		{{a}_{9}}=1\oplus 0\oplus 1\oplus 1=1\\
		{{a}_{10}}=1\oplus 1\oplus 1\oplus 0=1
		$
		可以得到输出序列为 $\left( 1101111011\cdots  \right)$，周期为p=5 。
	}
	
	
	\begin{Exercise}
		设密钥流是由m=2s 级的LFSR产生，其前 m+2个比特是${{(01)}^{s+1}}$ ,即 s+1个01。问第m+3个比特有无可能是1，为什么？.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		第m+3个比特上不可能出现1，下面说一下理由。\par
		根据线性移位寄存器的的递推关系有：\\
		$
		 {{a}_{2s+1}}={{c}_{1}}{{a}_{2s}}\oplus {{c}_{2}}{{a}_{2s-1}}\oplus \cdots \oplus {{c}_{2s}}{{a}_{1}}=0 \\ 
		 {{a}_{2s+2}}={{c}_{1}}{{a}_{2s+1}}\oplus {{c}_{2}}{{a}_{2s}}\oplus \cdots \oplus {{c}_{2s}}{{a}_{2}}=1
		$\\
		从而有
		$
		 {{a}_{1}}=0,{{a}_{2}}=1\cdots {{a}_{2s+1}}=0,{{a}_{2s+2}}=1
		$，
		代入下式有：\\
		$
		 {{a}_{2s+3}}={{c}_{1}}{{a}_{2s+2}}\oplus {{c}_{2}}{{a}_{2s+1}}\oplus \cdots \oplus {{c}_{2s}}{{a}_{3}}=0 
		$
	}

	\begin{Exercise}
		设密钥流是由n级LFSR产生，其周期为 ${{2}^{n}}-1$ , i是任一整数，在密钥流中考虑以下比特对：\\
		$({{S}_{i}},{{S}_{i+1}}),({{S}_{i+1}},{{S}_{i+2}}),...({{S}_{i+{{2}^{n}}-3}},{{S}_{i+{{2}^{n}}-2}}),({{S}_{i+{{2}^{n}}-2}},{{S}_{i+{{2}^{n}}-1}})$\\
		问有多少形如$({{S}_{j}},{{S}_{j+1}})=(1,1)$ 的比特对。试证明你的结论。
		.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		根据p23定理2-7，在GF(2)上的n长m	序列在周期为${{2}^{n}}-1$ 的m序列中对于 $1\le i\le n-2$,长为i的游程有${{2}^{n-i-1}}$ 个，且0，1游程各半，那么就有：\\
		1的2游程： ${{2}^{n-2-1}}/2={{2}^{n-4}}$\\
		1的3游程： ${{2}^{n-3-1}}/2={{2}^{n-5}}$\\
		……\\
		1的n-2游程：${{2}^{n-(n-2)-1}}/2=1$ \\
		那么就有：\\
		$S={{2}^{n-4}}+{{2}^{n-5}}\cdot 2+{{2}^{n-6}}\cdot 3+\cdots \cdots +2\cdot (n-4)+1\cdot (n-3)$ (1式)\\
		(1式)/2得:\\
		$\frac{1}{2}s={{2}^{n-5}}+{{2}^{n-6}}\cdot 2+\cdots \cdots +(n-4)+(n-3)/2$ (2式)\\
		由1式，2式得：\\
		$\frac{1}{2}s={{2}^{n-4}}+{{2}^{n-5}}+\cdots \cdots +1-(n-3)/2$\\
		从而有 $S={{2}^{n-2}}-2-n+3={{2}^{n-2}}-n+1$
		即共有${{2}^{n-2}}-n+1$ 个形如 $({{S}_{j}},{{S}_{j+1}})=(1,1)$的比特对。
		
	}

%	\begin{Exercise}
%		已知流密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。.\cite{yang-mcry}
%	\end{Exercise}
%	\jd{
%		由已知可得相应的密钥流序列为1110100111，又因为是3级线性反馈移位寄存器，可得以下方程：\\
%		$\left( {{a}_{4}}{{a}_{5}}{{a}_{6}} \right)=\left( {{c}_{3}}{{c}_{2}}{{c}_{1}} \right)\left( \begin{matrix}
%			{{a}_{1}} & {{a}_{2}} & {{a}_{3}}  \\
%			{{a}_{2}} & {{a}_{3}} & {{a}_{4}}  \\
%			{{a}_{3}} & {{a}_{4}} & {{a}_{5}}  \\
%		\end{matrix} \right)$
%		\\
%		将值代入得:\\
%		$\left( 010 \right)=\left( {{c}_{3}}{{c}_{2}}{{c}_{1}} \right)\left( \begin{matrix}
%			1 & 1 & 1  \\
%			1 & 1 & 0  \\
%			1 & 0 & 1  \\
%		\end{matrix} \right)$
%		\\
%		${{\left( \begin{matrix}
%				1 & 1 & 1  \\
%				1 & 1 & 0  \\
%				1 & 0 & 1  \\
%				\end{matrix} \right)}^{-1}}=\frac{{{A}^{*}}}{\left| A \right|}$,
%		$\left| A \right|=\left| \begin{matrix}
%		1 & 1 & 1  \\
%		1 & 1 & 0  \\
%		1 & 0 & 1  \\
%		\end{matrix} \right|=1
%		\Rightarrow 
%		{{\left( \begin{matrix}
%				1 & 1 & 1  \\
%				1 & 1 & 0  \\
%				1 & 0 & 1  \\
%				\end{matrix} \right)}^{-1}}=\left( \begin{matrix}
%		1 & 1 & 1  \\
%		1 & 0 & 1  \\
%		1 & 1 & 0  \\
%		\end{matrix} \right)
%		 $\\
%		 $\left( {{c}_{3}}{{c}_{2}}{{c}_{1}} \right)=\left( 010 \right)\left( \begin{matrix}
%		 1 & 1 & 1  \\
%		 1 & 0 & 1  \\
%		 1 & 1 & 0  \\
%		 \end{matrix} \right)=\left( 101 \right)
%		 $
%		 \\
%		 由此可得密钥流的递推关系为：\\
%		 ${{a}_{i+3}}={{c}_{3}}{{a}_{i}}\oplus {{c}_{1}}{{a}_{i+2}}={{a}_{i}}\oplus {{a}_{i+2}}$
%	}

	\begin{Exercise}
		若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器，产生的密钥是m序列。2.5节已知，敌手若知道一段长为2n的明密文对就可破译密钥流生成器。若敌手仅知道长为2n-2的明密文对，问如何破译密钥流生成器。.\cite{yang-mcry}
	\end{Exercise}
	\jd{
		如果敌手仅仅知道长为2n-2的明密文对，他可以构造出以下的长为2n的明密文对：
		不妨设：\par
		明文：${{x}_{1}}{{x}_{2}}...{{x}_{2n-2}}{{x}_{2n-1}}{{x}_{2n}}$ \par
		密文：${{y}_{1}}{{y}_{2}}...{{y}_{2n-2}}{{y}_{2n-1}}{{y}_{2n}}$\par
		其中：\par
		${{x}_{1}}\cdots \cdots {{x}_{2n-2}}$ 为已知的， ${{x}_{2n-1,}}{{x}_{2n}}$为未知的。\par
		${{y}_{1}}\cdots \cdots {{y}_{2n-2}}$为已知的， ${{y}_{2n-1,}}{{y}_{2n}}$为未知的。\par
		
		 $({{y}_{2n-1,}}{{y}_{2n}})$的可能取值为{00,01,10,11}。 $({{x}_{2n-1,}}{{x}_{2n}})$的可能取值为{00,01,10,11}。共有16种组合方案，分别破解得到密钥流，在破解的结果中符合m序列的性质密钥流即为正确的方案，有可能不唯一。
		
	}

	\begin{Exercise}
		设J-K触发器中 $\left\{ {{a}_{k}} \right\}$和$\left\{ {{b}_{k}} \right\}$ 分别为3级和4级m序列，且 $\left\{ {{a}_{k}} \right\}=11101001110100\cdots, \left\{ {{b}_{k}} \right\}=001011011011000001011011011000\cdots$， 求输出序列 $\left\{ {{c}_{k}} \right\}$ 及周期。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由J-K触发器可知 ${c}_{k}=\left( {a}_{k}+{b}_{k}+1 \right){c}_{k-1}+{a}_{k}$，
		$
		c_k=\lbrace
		\begin{matrix}
			{a}_{k} ,c_{k-1}=0 \\
			\overline{{b}_{k}} , c_{k-1}=1\\
		\end{matrix} 
		$
		\par
		此时 $\left\{ {a}_{k} \right\}$和 $\left\{ {b}_{k} \right\}$分别为3级和4级m序列，$\left( 3,4 \right)  =1$则 $\left\{ {c}_{k} \right\}$的周期为 $\left( 2^3-1 \right) \left( 2^4-1 \right)=7\times 15=105$。
		\par
		$\left\{ c_k \right\}=11001001010100\cdots$
	}

	\begin{Exercise}
		设基本钟控序列生成器中$\left\{ {{a}_{k}} \right\}$ 和 $\left\{ {{b}_{k}} \right\}$分别为2级和3级m序列，且 $\left\{ {{a}_{k}} \right\}=101101\cdots,\left\{ {{b}_{k}} \right\}=10011011001101\cdots$， 求输出序列$\left\{ {{c}_{k}} \right\}$ 及周期。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		令基本钟控序列生成器中$\left\{ {{a}_{k}} \right\}$ 的周期为 $p_1$， $\left\{ {{b}_{k}} \right\}$的周期为$p_2$ ，则输出序列$\left\{ {{c}_{k}} \right\}$ 的周期为 $p=\frac{{{p}_{1}}{{p}_{2}}}{\gcd \left( {{w}_{1}},{{p}_{2}} \right)},{{w}_{1}}=\sum\limits_{i=0}^{{{p}_{1}}-1}{{{a}_{i}}=2},{{p}_{1}}={{2}^{2}}-1=3,{{p}_{2}}={{2}^{3}}-1=7 \Rightarrow p=\frac{3\times 7}{\gcd (2,7)}=21 $。\par
		
		记LFSR2产生$\left\{ {{b}_{k}} \right\}$ ，其状态向量为${\sigma }_{k}$ ，可得${\sigma }_{k}$ 的变化情况如下：\par
		${{\sigma }_{0}}{{\sigma }_{1}}{{\sigma }_{1}}{{\sigma }_{2}}{{\sigma }_{3}}{{\sigma }_{3}}{{\sigma }_{4}}{{\sigma }_{5}}{{\sigma }_{5}}{{\sigma }_{6}}{{\sigma }_{0}}{{\sigma }_{0}}{{\sigma }_{1}}{{\sigma }_{2}}{{\sigma }_{2}}{{\sigma }_{3}}{{\sigma }_{4}}{{\sigma }_{4}}{{\sigma }_{5}}{{\sigma }_{6}}{{\sigma }_{6}}{{\sigma }_{0}}{{\sigma }_{1}}{{\sigma }_{1}}{{\sigma }_{2}}$
		\par
		输出序列$\left\{ {c}_{k} \right\}=100011100111000111011\cdots$.
		
	}

	\begin{Exercise}
		Geffe序列发生器由3个LFSR组成，这些LFSR的长度分别为$n_i \quad i=1,2,3$,其输出序列均为m序列，则Geffe序列产生器的线性复杂度是多少？\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{($n_1 +n_3) n_2 +n_3$}
	
\chapter{分组密码}
	\begin{Exercise}
		什么是Feistel结构？
	\end{Exercise}
	\jd{
	}
	
	\begin{Exercise}
	分组密码设计的基本原则？
	\end{Exercise}
	\jd{混淆和扩散}
	
	\begin{Exercise}
		除了混淆和扩散原则，分组密码算法还应满足得要求有哪些？
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		\begin{enumerate}
			\item 分组长度n要足够大：防止明文穷举攻击法奏效。
			\item 密钥量要足够大：尽可能消除弱密钥，并使所有密钥同等地好，以防止密钥穷举攻击奏效。
			\item 由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。
			\item 加密和解密运算简单：易于软件和硬件高速实现。
			\item 数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时，可引入数据扩展。
		\end{enumerate}
	}
	
	\begin{Exercise}
		请简述常用的五种分组密码的工作方式。
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		\begin{enumerate}
			\item 电码本(ECB):直接利用加密算法分别对分组数据组加密。
			\item 密码分组链接模式(CBC):先将明文分组与上一次的密文块进行按比特异或，然后进行加密处理。
			\item 密码反馈模式(CFB):若待加密消息需按字符、字节或比特处理时，可采用CFB模式。
			\item 输出反馈模式(OFB):在结构熵类似CFB模式，但其反馈的内容是DES的输出，而不是密文。
			\item 计数器模式：可以看做是OFM模式的简化版本，其输入由计数器来更新。
		\end{enumerate}
	}
	
	
	
	\begin{Exercise}
		(1) 设M’和M的逐比特取补，证明在DES中，如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即：\par
		如果$Y=DES_K(X)$，那么$Y’=DES_{K’}(X’)$
		\par
		提示：对任意两个长度相等的比特串A和B，证明${{A\oplus B}}^{'}=A'\oplus B$ 。
		\par
		(2) 对DES进行穷搜索攻击时，需要在由$2^{56}$个密钥构成的密钥空间进行，能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)设$L_i$和$R_i$分别是第i轮DES变换的左右部分，$i=0,1,…,16$, 则加密过程为:\\
		${{L}_{0}} {{R}_{0}}\leftarrow IP \\ 
		 {{L}_{i}}\leftarrow {{R}_{i-1}} \\ 
		 {{R}_{i}}\leftarrow {{L}_{i-1}}\oplus f({{R}_{i-1}},{{K}_{i}}) \\ 
		 64bit cipher\leftarrow I{{P}^{-1}}({{R}_{16}}{{L}_{16}}) \\ 
		$
		若将明文和密钥k同时取补，则加密过程为：
		$
		 L_{_{0}}^{'} R_{_{0}}^{'}\leftarrow IP \\ 
		 L_{i}^{'}\leftarrow R_{i-1}^{'}  \\ 
		 R_{i}^{'}\leftarrow L_{i-1}^{'}\oplus f(R_{i-1}^{'},K_{i}^{'}) \\ 
		 64bit cipher\leftarrow I{{P}^{-1}}(R_{16}^{'}L_{16}^{'}) \\ 
		$
		其中，$f({{R}_{i-1}},{{K}_{i}})$ 的作用是将数据的左、右半部分扩展后与密钥进行逐比特异或运算，因此 $f({{R}_{i-1}},{{K}_{i}})=f(R{{'}_{i-1}},K{{'}_{i}})$，再经过S盒，并将输出结果进行置换运算P之后有：$R{{'}_{i}}\leftarrow L{{'}_{i-1}}\oplus f(R{{'}_{i-1}},K{{'}_{i}})=L{{'}_{i-1}}\oplus f({{R}_{i-1}},{{K}_{i}})$ ，而 ${{R}_{i}}\leftarrow {{L}_{i-1}}\oplus f({{R}_{i-1}},{{K}_{i}})$，所以有 $R{{'}_{i}}={{\bar{R}}_{i}}$。同时有$L{{'}_{i}}={{\bar{L}}_{i}}$ ，所以明文P与密钥K同时取补后有$Y'=DE{{S}_{k'}}(x')$ 。
		\par
		(2)根据(1)的结论进行穷搜索攻击, 可将待搜索的密钥空间减少一半，即$2^55$个。因为给定明文x，则 ${{Y}_{1}}=DE{{S}_{k}}(x)$，由(1)知 ${{Y}_{2}}=DE{{S}_{k'}}(x')={{\bar{Y}}_{1}}$，则一次搜索就包含了x和x’ 两种明文情况。
	}

	\begin{Exercise}
		证明DES解密变换是加密变换的逆。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		令 $T(L,R)=(R,L)$为左右位置交换函数，${{F}_{ki}}=(L\oplus f(R,ki),R)$ ,则第i次迭代变换为:${{T}_{ki}}=T{{F}_{ki}}=T(L\oplus f(R,ki),R)=(\text{R},L\oplus f(R,ki))$\par
		
		又因为${{\text{T}}^{2}}(L,R)=T(R,L)=I(L,R)$，有$T=T^{-1}$\par
		同时，$F_{ki}^{2}(L,R)={{F}_{ki}}(L\oplus f(R,ki),R)=(L\oplus f(R,ki)\oplus f(R,ki),R)=(L,R)$，即，${{F}_{ki}}=F_{ki}^{-1}$\par
		
		所以有，$({{F}_{ki}}T)(T{{F}_{ki}})={{F}_{ki}}{{F}_{ki}}=I\Rightarrow {{(T{{F}_{ki}})}^{-1}}={{F}_{ki}}T$\par
		
		DES加密过程在密钥k作用下为:\par
		$DE{{S}_{k}}=I{{P}^{-1}}{{F}_{k16}}T{{F}_{k15}}T\cdots {{F}_{k2}}T{{F}_{k1}}(IP)$
		\par
		
		解密过程为: \par
		$DE{{S}_{k}}^{-1}=I{{P}^{-1}}{{F}_{k1}}T{{F}_{k2}}T\cdots {{F}_{k15}}T{{F}_{k16}}(IP)$
		\par
		
		所以，$(DE{{S}_{k}}^{-1})(DE{{S}_{k}})=I$,即解密变换是加密变换的逆。（得证）
	}

	\begin{Exercise}
		在DES的EBC模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组
		受到影响。然而在CBC模式中，将有错误传播。例如在图3-11中C1中的一个错误明显地将影响P1和P2的结果。\par
		(1)  P2后的分组是否受到影响？\par
		(2) 设加密前的明文分组P1中有一个比特的错误，问这一错误将在多少个密文分组中传播？对接收者产生什么影响？
		。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)在CBC模式中，若密文分组中有一个错误$C_1$，则解密时明文分组中$P_1,P_2$ 都将受到影响，而$P_{2+i}(i=1,2,\cdots)$ 后的分组都不受影响，即CBC的错误传播长度为2，具有自恢复能力。
		\par
		(2)若明文分组$P_1$有错误，则以后的密文分组都将出现错误，但对接收者来说，经过解密后，除$P_1$有错误外，其余的明文分组都能正确恢复。
	}

	\begin{Exercise}
		在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远？\cite{yang-mcry}
	\end{Exercise}
	\jd{
		在8比特CFB模式中，若密文有1比特错误，则会影响当前分组以及后续分组的解密，会使解密输出连续9组出错，即错误传播的长度为9。
	}

	\begin{Exercise}
		在实现IDEA时，最困难得部分是模$2^{16}+1$ 乘法运算。以下关系给出了实现模乘法的一种有效方法，其中a和b是两个n比特的非0整数：\par
		(1) 证明存在唯一的非负整数q和r使得 $ab=q({{2}^{n}}+1)+r$；\par
		(2) 求q和r的上下界；\par
		(3) 证明$q+r<{{2}^{n+1}}$ ;\par
		(4) 求 $ab div 2^n$关于q的表达式；\par
		(5) 求 $ab mod 2^n$关于q和r的表达式；\par
		(6) 用(4)和(5)的结果求r的表达式，说明r的含义。		
		。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)	假设存在 ${{q}_{1}},{{r}_{1}},{{q}_{2}},{{r}_{2}}$使得$ab={{q}_{1}}({{2}^{n}}+1)+{{r}_{1}}={{q}_{2}}({{2}^{n}}+1)+{{r}_{2}}$ ，有 $({{q}_{1}}-{{q}_{2}})({{2}^{n}}+1)={{r}_{1}}-{{r}_{2}},$ 因为 $0\le {{r}_{1}},{{r}_{2}}\le {{2}^{n}}$，所以 $|{{r}_{1}}-{{r}_{2}}|\le {{2}^{n}}$.\par
		因此，只能有${{r}_{1}}={{r}_{2}},{{q}_{1}}={{q}_{2}}$.(得证)
		\par
		(2)$0\le r=ab\bmod ({{2}^{n}}+1)\le {{2}^{n}}$
		\par
		显然，a和b的最大值均为$2^n -1$ ，则有$\frac{{{a}_{\max }}\times {{b}_{\max }}}{{{2}^{n}}+1}=\frac{{{2}^{2n}}-{{2}^{n+1}}+1}{{{2}^{n}}+1}=\frac{\left( {{2}^{n}}\left( {{2}^{n}}+1 \right)-2\times \left( {{2}^{n}}+1 \right)+2-{{2}^{n}}-1 \right)}{{{2}^{n}}+1}={{2}^{n}}-3$
		\par
		所以有：\par
		$\left\{ \begin{matrix}
		\text{0}\le q\le {{2}^{n}}-3,if(n\ge 2)  \\
		q=0,if(n=1)  \\
		\end{matrix} \right.$
		\par
		
		(3) $q+r\le {{2}^{n}}+{{\text{2}}^{n}}-3<{{2}^{n+1}}$
		\par
		
		(4)根据$ab=q({{2}^{n}}+1)+r$ ，得
		$(ab)div{{2}^{n}}=\left\{ \begin{matrix}
		q & if(q+r)<{{2}^{n}}  \\
		q+1 & if(q+r)>{{2}^{n}}  \\
		\end{matrix} \right.$
		\par
		
		(5)根据$ab=q({{2}^{n}}+1)+r$ ，得
		$(ab)\bmod {{2}^{n}}=\left\{ \begin{matrix}
		q+r & if(q+r)<{{2}^{n}}  \\
		(q+r)\bmod {{2}^{n}} & if(q+r)>{{2}^{n}}  \\
		\end{matrix} \right.$
		\par
		
		(6)当 $ab=q({{2}^{n}}+1)+r$时，根据 $(ab)div{{2}^{n}}=q$及 $(ab)\bmod {{2}^{n}}=q+r$得:
		$r=(ab\bmod {{2}^{n}})-(abdiv{{2}^{n}})$
		\par
		同理，当$q+r\ge {{2}^{n}}$ 时，有：\par
		$r=(ab\bmod {{2}^{n}})-(abdiv{{2}^{n}})+{{\text{2}}^{n}}+1$
		\par
		余数r表示ab的n个最低有效位与ab右移位数n之差。
		
	}

	\begin{Exercise}
		(1) 在IDEA的模乘运算中，为什么将模乘取为 而不是 ？\par
		(2) 在IDEA的模加运算中，为什么将模乘取为 而不是 ？
		。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1) 在IDEA模乘运算中，必须保证运算构成一个群，因此模数必须为素数，故不能取$2^{16}$。\par
		(2) 同一群内的分配律和结合律都成立，但IDEA算法中要保证模数的加法和模数的乘法，比特异或之间分配律和结合律不成立，因此模加运算不能和模乘运算在同一个群内，即不能选模$2^{16}+1$，而$2^{16}$在模加运算中必为一个群.
	}

	\begin{Exercise}
		证明SM4算法满足对合性，即加密过程和解密过程一样，只是密钥使用的顺序相反。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		SM4算法的加密轮函数分为加密函数G和数据交换E。其中G对数据进行加密处理，E进行数据顺序交换。即加密轮函数:\par
		\begin{center}
			$F_i=G_i E$
		\end{center}
		
		\par
		其中：\par
		$G_i = G_i(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)\quad (i=0,1,2,…,31)\\
		=(X_i \oplus T( X_{i+1},X_{i+2},X_{i+3},rk_i),X_{i+1},X_{i+2},X_{i+3})
		$
		\par
		$E(X_{i+4},(X_{i+1},X_{i+2},X_{i+3}))=((X_{i+1},X_{i+2},X_{i+3}),X_{i+4}) \quad (i=0,1,2,…,31) $
		\par
		因为有：\par
		$(G_i)^2=G_i(X_i \oplus T(X_{i+1},X_{i+2},X_{i+3},rk_i),X_{i+1},X_{i+2},X_{i+3},rk_i)\\
		=(X_i \oplus T(X_{i+1},X_{i+2},X_{i+3},rk_i) \oplus T(X_{i+1},X_{i+2},X_{i+3},rk_i), X_{i+1},X_{i+2},X_{i+3},rk_i)\\
		=(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i)\\
		=I
		$
		\par
		因此，加密函数G是对合得。\par
		E变换为：\par
		$E(X_{i+4},(X_{i+1},X_{i+2},X_{i+3}))\\
		=((X_{i+1},X_{i+2},X_{i+3}),X_{i+4})
		$
		\par
		$E^2 (X_{i+4},(X_{i+1},X_{i+2},X_{i+3})) =I$\par
		显然，E是对合运算。\par
		综上，加密轮函数是对合的。\par
		根据加密框图，可将SM4的加密过程写为：\par
		\begin{center}
			$SM4=G_0 EG_1 E \ldots G_{30} EG_{31} R$
		\end{center}
		\par
		根据解密框图，可将SM4的解密过程写为：\par
		\begin{center}
			$SM4^{-1}=G_{31} EG_{30} E…G_1 EG_0 R$ 
		\end{center}
		\par
		比较SM4与$SM4^{-1}$可知，运算相同，只有密钥的使用顺序不同。\par
		所以，SM4算法是对合的。
	}
\chapter{数论基本练习}
	\begin{Exercise}
		证明：群G是交换群的充要条件是对任意的$a,b \in G$，有$(ab)^2 =a^2b^2$。
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		必要性：若G是交换群，则对任意$a,b\in G$，有$ab=ba$，从而$(ab)^2=abab=aabb=a^2b^2$.\par
		充分性：若对任意$a,b \in G$,有$(ab)^2=a^2b^2$,那么$ba=ebae=a^{-1}ababb^{-1}=a^{-1}(ab)^2b^{-1}=a^{-1}ababb^{-1}=ebae=ba$.
	}
	
	\begin{Exercise}
		证明：如果a是整数，则$a^3 -a$一定能被3整除。
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		$\because a^3-a=(a-1)a(a+1)$\par
		当$a=3k,k \in \mathbb{Z}$,则$(a-1)a(a+1)=(3k-1)3k(3k+1)$，一定能被3整除。\par
		当$a=3k-1,k \in \mathbb{Z}$,则$(a-1)a(a+1)=(3k-2)(3k-1)3k$，一定能被3整除。\par
		当$a=3k+1,k \in \mathbb{Z}$,则$(a-1)a(a+1)=3k(3k+1)(3k+2)$，一定能被3整除。\par
		综上所述，$a^3 -a$一定能被3整除。
	}

	


	\begin{Exercise}
		证明以下关系：\par
		(1) $a \pmod n = b \pmod n \Rightarrow a =b \pmod n$ \par
		(2) $a\equiv b\bmod n$，则$b\equiv a\bmod n$；\par
		(3) $a\equiv b\bmod n$，$b\equiv c\bmod n$，则$a\equiv c\bmod n$\par
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)设$a\bmod n={{r}_{a}},b\bmod n={{r}_{b}}$，由题意得${{r}_{a}}={{r}_{b}}$，且存在整数$j,k$，使得
		$a=jn+{{r}_{a}},b=kn+{{r}_{b}}\Rightarrow a-b=(j-k)n$，即$n|a-b$，证得$a\equiv b\bmod n$。
		\par
		(2)已知$a\equiv b\bmod n$，则存在整数$k$，使得$a=kn+b\Rightarrow b=(-k)n+a$，证得$b\equiv a\bmod n$。
		\par
		(3)已知$a\equiv b\bmod n,b\equiv c\bmod n$，则存在整数$j,k$，使得
		$a=jn+b,b=kn+c\Rightarrow a=(j+k)n+c$，证得$a\equiv c\bmod n$。
		
	}

	\begin{Exercise}
		证明以下关系：\par
		(1) $[(a\bmod n)-(b\bmod n)]\bmod n=(a-b)\bmod n$；\par
		(2) $[(a\bmod n)\times (b\bmod n)]\bmod n=(a\times b)\bmod n$。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)设$a\bmod n={{r}_{a}},b\bmod n={{r}_{b}}$，则存在整数$j,k$，使得
		$
		a=jn+{{r}_{a}},b=kn+{{r}_{b}}\Rightarrow a-b=(j-k)n+({{r}_{a}}-{{r}_{b}}) \\ 
		 \Rightarrow {{r}_{a}}-{{r}_{b}}=-(j-k)n+(a-b) \\ 
		 \Rightarrow ({{r}_{a}}-{{r}_{b}})\bmod n=(a-b)\bmod n. \\ 
		$
		即$[(a\bmod n)-(b\bmod n)]\bmod n=(a-b)\bmod n$。
		(2)设$a\bmod n={{r}_{a}},b\bmod n={{r}_{b}}$，则存在整数$j,k$，使得
		$ a=jn+{{r}_{a}},b=kn+{{r}_{b}}\Rightarrow a\times b=(jkn+j{{r}_{b}}+k{{r}_{a}})n+{{r}_{a}}{{r}_{b}} \\ 
		 \Rightarrow {{r}_{a}}{{r}_{b}}=-(jkn+j{{r}_{b}}+k{{r}_{a}})n+(a\times b) \\ 
		 \Rightarrow ({{r}_{a}}{{r}_{b}})\bmod n=(a\times b)\bmod n. \\ 
		$
		即$[(a\bmod n)\times (b\bmod n)]\bmod n=(a\times b)\bmod n$。
		
	}

	\begin{Exercise}
		用Fermat定理求${{3}^{201}}\bmod 11$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为$p=11$是素数，且$\gcd (311)1$，则由Fermat定理可得：
		${{3}^{10}}\equiv 1\bmod 11\Rightarrow {{({{3}^{10}})}^{k}}\equiv 1\bmod 11$；
		又根据性质$[(a\bmod n)\times (b\bmod n)]\bmod n=(a\times b)\bmod n$，可得：
		${{3}^{201}}\bmod 11=[({{({{3}^{10}})}^{20}})\bmod 11)\times ({{3}^{1}}\bmod 11)]\bmod 11=3\bmod 11$。
				
	}

 
	\begin{Exercise}
		用推广的Euclid算法求$67 \pmod 119$ 的逆元。。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		运算步骤如下表所示：\par
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline 
			循环次数&	Q&	X1&	X2&	X3&	Y1&	Y2&	Y3 \\ 
			\hline 
			初值&	\~{}&	1&	0&	119&	0&	1&	67  \\ 
			\hline 
			1&	1&	0&	1&	67&	1&	-1&	52  \\ 
			\hline 
			2&	1&	1&	-1&	52&	-1&	2&	15  \\ 
			\hline 
			3&	3&	-1&	2&	15&	4&	-7&	7 \\ 
			\hline 
			4&	2&	4&	-7&	7&	-9&	16&	1  \\ 
			\hline 
		\end{tabular} 
	\par
	所以${{67}^{-1}}\bmod 119=16$。
		
	}
 
 
	\begin{Exercise}
		求$\gcd (4655,12075)$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由Euclid算法，得：
		$ 12075=2\times 4655+2765 \\ 
		 4655=1\times 2765+1890 \\ 
		 2765=1\times 1890+875 \\ 
		 1890=2\times 875+140 \\ 
		 875=6\times 140+35 \\ 
		 140=4\times 35+0 \\ 
		$
		\par
		所以$\gcd (4655,12075)=35$。	
	}

 
	\begin{Exercise}
		求解下列同余方程组\cite{yang-mcry}：$\left\{ \begin{matrix}
		x\equiv 2\bmod 3  \\
		x\equiv 1\bmod 5  \\
		x\equiv 1\bmod 7  \\
		\end{matrix} \right.$
	\end{Exercise}
	\jd{
		根据中国剩余定理求解该同余方程组，记${{a}_{1}}=2,{{a}_{2}}=1,{{a}_{3}}=1{{m}_{1}}=3,{{m}_{2}}=5,{{m}_{3}}=7$，$M={{m}_{1}}\times {{m}_{2}}\times {{m}_{3}}\text{=}105$，则有:\par
		$
		 {{M}_{1}}=\frac{M}{{{m}_{1}}}=35,M_{1}^{-1}\bmod {{m}_{1}}={{35}^{-1}}\bmod 3=2, \\
		 {{M}_{2}}=\frac{M}{{{m}_{2}}}=21,M_{2}^{-1}\bmod {{m}_{2}}={{21}^{-1}}\bmod 5=1, \\ 
		 {{M}_{3}}=\frac{M}{{{m}_{3}}}=15,M_{3}^{-1}\bmod {{m}_{3}}={{15}^{-1}}\bmod 7=1.  
		$\par
		所以方程组的解为:\par
		$
		 x\equiv ({{M}_{1}}M_{1}^{-1}{{a}_{1}}+{{M}_{2}}M_{2}^{-1}{{a}_{2}}+{{M}_{3}}M_{3}^{-1}{{a}_{3}})\bmod M \\
		 \equiv (35\times 2\times 2+21\times 1\times 1+15\times 1\times 1)\bmod 105 \\ 
		 \equiv 176\bmod 105\equiv 71\bmod 105. \\ 
		$
		
	}

	\begin{Exercise}
		计算下列Legendre符号\cite{yang-mcry}：\par
		(1) $\left( \frac{2}{59} \right)$；\par		
		(2) $\left( \frac{6}{53} \right)$；\par		
		(3) $\left( \frac{65}{107} \right)$
		
	\end{Exercise}
	\jd{
		(1)$\left( \frac{2}{59} \right)={{(-1)}^{\frac{{{59}^{2}}-1}{8}}}=-1$
		\par
		(2)
		$ \left( \frac{6}{53} \right)\left( \frac{2}{53} \right)\left( \frac{3}{53} \right){{\left( 1 \right)}^{\frac{{{53}^{2}}1}{8}}}\left( \frac{3}{53} \right)(1)\left( \frac{53}{3} \right) \\ 
		 =(-1)\left( \frac{2+17\times 3}{3} \right)=(-1)\left( \frac{2}{3} \right)=(-1){{(-1)}^{\frac{{{3}^{2}}-1}{8}}} \\ 
		 =1 \\ 
		$
		\par
		(3)
		$ \left( \frac{65}{107} \right)=\left( \frac{107}{65} \right)=\left( \frac{42}{65} \right)=\left( \frac{6}{65} \right)\left( \frac{7}{65} \right)=\left( \frac{2}{65} \right)\left( \frac{3}{65} \right)\left( \frac{7}{65} \right)={{(-1)}^{\frac{{{65}^{2}}-1}{8}}}\left( \frac{3}{65} \right)\left( \frac{7}{65} \right) \\ 
		 =\left( \frac{65}{3} \right)\left( \frac{65}{7} \right)=\left( \frac{2+21\times 3}{3} \right)\left( \frac{2+9\times 7}{7} \right)=\left( \frac{2}{3} \right)\left( \frac{2}{7} \right)={{(-1)}^{\frac{{{3}^{2}}-1}{8}}}{{(-1)}^{\frac{{{7}^{2}}-1}{8}}} \\ 
		 =-1 \\ 
		$		
	}

 
	\begin{Exercise}
		求25 的所有本原根。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为$\varphi (25)=25(1-\frac{1}{5})=20={{2}^{2}}\times 5$，所以$\varphi (25)$的所有不同的素因子为${{q}_{1}}=2,{{q}_{2}}=5$，即对每个$g$，只需计算${{g}^{10}}{{g}^{4}}$。又因为$\varphi (24)=24(1-\frac{1}{2})(1-\frac{1}{3})=8$，所以$25$有8个本原根。
		$ {{1}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{1}^{4}}=1\bmod 25 \\ 
		 {{3}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{3}^{4}}=6\bmod 25 \\ 
		 {{5}^{10}}=0\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{5}^{0}}=0\bmod 25 \\ 
		 {{7}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{7}^{4}}=1\bmod 25 \\ 
		 {{9}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{9}^{4}}=11\bmod 25 \\ 
		 {{11}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{11}^{4}}=16\bmod 25 \\ 
		 {{13}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{13}^{4}}=11\bmod 25 \\ 
		 {{15}^{10}}=0\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{15}^{4}}=0\bmod 25 \\ 
		 {{17}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{17}^{4}}=21\bmod 25 \\ 
		 {{19}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{19}^{4}}=21\bmod 25 \\ 
		 {{21}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{21}^{4}}=6\bmod 25 \\ 
		 {{23}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{23}^{4}}=16\bmod 25 \\ 
		$	
			
		$ {{2}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{2}^{4}}=16\bmod 25 \\ 
		 {{4}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{4}^{4}}=6\bmod 25 \\ 
		 {{6}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{6}^{4}}=21\bmod 25 \\ 
		 {{8}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{8}^{4}}=21\bmod 25 \\ 
		 {{10}^{10}}=0\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{10}^{4}}=0\bmod 25 \\ 
		 {{12}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{12}^{4}}=11\bmod 25 \\ 
		 {{14}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{14}^{4}}=16\bmod 25 \\ 
		 \text{1}{{6}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{16}^{4}}=11\bmod 25 \\ 
		 {{18}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{18}^{4}}=1\bmod 25 \\ 
		 {{20}^{10}}=0\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{20}^{4}}=0\bmod 25 \\ 
		 {{22}^{10}}=24\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{22}^{4}}=6\bmod 25 \\ 
		 {{24}^{10}}=1\bmod 25\begin{matrix}
		{}  \\
		\end{matrix}{{24}^{4}}=1\bmod 25 \\ 
		$
		\par
		满足${{g}^{10}}\ne 1\bmod 25$且${{g}^{4}}\ne 1\bmod 25$的$g$为$25$的本原根，即$2,3,8,12,13,17,22,23$。
	}

 
	\begin{Exercise}
		证明当且仅当$n$是素数时，$<{{Z}_{n}},{{+}_{n}},{{\times }_{n}}>$是域。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)若$<{{Z}_{n}},{{+}_{n}},{{\times }_{n}}>$是域，则$<{{Z}_{n}},{{+}_{n}}>$，$<{{Z}_{n}}-\{\text{0}\},{{\times }_{n}}>$均为Abel群。显然$<{{Z}_{n}},{{+}_{n}}>$为Abel群，与n是否为素数无关；但若$<{{Z}_{n}}-\{\text{0}\},{{\times }_{n}}>$为Abel群，其条件之一必须保证对任意$x\in {{Z}_{n}}-\{\text{0}\}$有模乘法逆元，即对任意$x\in {{Z}_{n}}-\{\text{0}\}$，有$y\in {{Z}_{n}}-\{\text{0}\}$，使得$x\times y\equiv \text{1}\bmod n$，所以$\gcd (x,n)=1$，即$\varphi (n)=n-1$，$n$为素数。
		\par
		(2)若$n$不是素数，则$\varphi (n)<n-1$，即至少存在一个$x\in {{Z}_{n}}-\{\text{0}\}$，使得$\gcd (x,n)\ne \text{1}$，即$x$无模乘法逆元，因此不能保证$<{{Z}_{n}}-\{\text{0}\},{{\times }_{n}}>$均为Abel群，即$<{{Z}_{n}},{{+}_{n}},{{\times }_{n}}>$不是域。
		
		
	}

\chapter{公钥密码体制}
 
	\begin{Exercise}
		设通信双方使用RSA加密体制，接收方的公开钥是$(e,n)=(5,35)$，接收到的密文是$C=10$，求明文$M$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为$n=35=5\times 7\Rightarrow p=5,q=7$，则$\varphi (n)=(p-1)\left( q-1 \right)=4\times 6=24$，所以
		$d\equiv {{e}^{-1}}\bmod \varphi (n)\equiv {{5}^{-1}}\bmod 24\equiv 5\bmod 24$，即明文$M\equiv {{C}^{d}}\bmod n\equiv {{10}^{5}}\bmod 35\equiv 5$。
		
	}

 
	\begin{Exercise}
		已知${{c}^{d}}\bmod n$的运行时间是$O({{\log }^{3}}n)$，用中国剩余定理改进RSA的解密运算。如果不考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		RSA的两个大素因子$p,q$的长度近似相等，约为模数$n$的比特长度$\log n$的一半，即$(\log n)/2$，而在中国剩余定理中，需要对模$p$和模$q$进行模指数运算，这与${{c}^{d}}\bmod n$的运行时间规律相似，所以每一个模指数运算的运行时间仍然是其模长的三次幂，即\[O[{{(\log n/2)}^{3}}]=O({{\log }^{3}}n)/8\]。
		在不考虑中国剩余定理计算代价的情况下，RSA解密运算的总运行时间为两个模指数运算的运行时间之和，即\[O({{\log }^{3}}n)/8+O({{\log }^{3}}n)/8=O({{\log }^{3}}n)/4\]，证得改进后的解密运算速度是原解密运算速度的4倍。
		
	}

 
	\begin{Exercise}
		设RSA加密体制的公开钥是$(e,n)=(77,221)$。\\
		(1) 用重复平方法加密明文$160$，得中间结果为：
		$ {{160}^{2}}(\bmod 221)\equiv 185 \\ 
		 {{160}^{4}}(\bmod 221)\equiv 191 \\ 
		 {{160}^{8}}(\bmod 221)\equiv 16 \\ 
		 {{160}^{16}}(\bmod 221)\equiv 35 \\ 
		 {{160}^{32}}(\bmod 221)\equiv 120 \\ 
		 {{160}^{64}}(\bmod 221)\equiv 35 \\ 
		 {{160}^{72}}(\bmod 221)\equiv 118 \\ 
		 {{160}^{76}}(\bmod 221)\equiv 217 \\ 
		 {{160}^{77}}(\bmod 221)\equiv 23 \\ 
		$
		\par
		若敌手得到以上中间结果就很容易分解$n$，问敌手如何分解$n$。\par
		(2) 求解密密钥d。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)由以上中间结果可得：\\
		$
		 {{160}^{16}}(\bmod 221)\equiv 35\equiv {{160}^{64}}(\bmod 221) \\ 
		 \Rightarrow {{160}^{64}}-{{160}^{16}}\equiv 0(\bmod 221) \\ 
		 \Rightarrow ({{160}^{32}}-{{160}^{8}})({{160}^{32}}+{{160}^{8}})\equiv 0(\bmod 221) \\ 
		 \Rightarrow (120-16)(120+16)\equiv 0(\bmod 221) \\ 
		 \Rightarrow 104\times 136\equiv 0(\bmod 221) \\ 
		$\par
		由$\gcd (104,221)=13,\gcd (136,221)=17$，可知分解为$221=13\times 17$。
		\par
		(2)解密密钥$d={{e}^{-1}}\bmod (\varphi (n))={{77}^{-1}}\bmod (\varphi (13\times 17))={{77}^{-1}}\bmod (12\times 16)$，由扩展的Eucild算法可得$d=5$。
	}
 
 	\begin{Exercise}
 		在Elgamal加密体制中，Alice和Bob使用p=17和g=3，Bob选择x=6做为他的私钥，试确定Bob的公钥。\\
 		当Alice取随机数k=10，试确定明文m=6的密文，并给出正确的解密过程。
 		\cite{mooc现代密码学聂旭云}
 	\end{Exercise}
 	\jd{
 		Bob的私钥$y=g^x \pmod {p}=3^6 \pmod {17}=15$。\par
 		明文m=6的密文$C_1 = g^k \pmod {p}=3^{10} \pmod{17}=8$\par
 		$C_2 = y^k \pmod {p}= 15^{10} \cdot 6 \pmod {17}=7$\par
 		解密过程为$m=C_2/C_1^x \pmod {p} = 15/8^6 \pmod {17} =7 \cdot 13 \pmod {17} =6$
 	}
 
 	
	\begin{Exercise}
		在ElGamal加密体制中，设素数$p=71$，本原根$g=7$，\\
		(1) 如果接收方B的公开钥是${{y}_{B}}=3$，发送方A选择的随机整数$k=2$，求明文$M=30$所对应的密文。\\
		(2) 如果A选择另一个随机整数$k$，使得明文$M=30$加密后的密文是$C=(59,{{C}_{2}})$，求${{C}_{2}}$。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)密文$C=({{C}_{1}},{{C}_{2}})$，其中：
		${{C}_{1}}={{g}^{k}}\bmod p={{7}^{2}}\bmod 71=49,{{C}_{2}}=({{y}_{B}}^{k}M)\bmod p=({{3}^{2}}\times 30)\bmod 71=57$。
		所以明文$M=30$对应的密文为$C=(49,57)$。\par
		(2)由${{C}_{1}}={{g}^{k}}\bmod p\Rightarrow 59={{7}^{k}}\bmod 71$，穷举法可得$k=3$。
		所以${{C}_{2}}=({{y}_{B}}^{k}M)\bmod p=({{3}^{3}}\times 30)\bmod 71=29$。
	}

 
	\begin{Exercise}
		设背包密码系统的超递增序列为$(3,4,9,17,35)$，乘数$t=19$，模数$k=73$，试对good night加密。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由$A=(3,4,9,17,35)$，乘数$t=19$，模数$k=73$，可得$B=t\times A\bmod k=(57,3,25,31,8)$。
		明文“good night”的编码为“00111”，“01111”，“01111”，“00100”，“00000”，“01110”，“01001”，“00111”，“01000”，“10100”，则有：\\
		$
		 f(00111)=25+31+8=64, \\ 
		 f(01111)=3+25+31+8=67, \\ 
		 f(01111)=3+25+31+8=67, \\ 
		 f(00100)=25, \\ 
		 f(00000)=0, \\ 
		 f(01110)=3+25+31=59, \\ 
		 f(01001)=3+8=11, \\ 
		 f(00111)=25+31+8=64, \\ 
		 f(01000)=3, \\ 
		 f(10100)=57+25=82=9\bmod 73. \\ 
		$
		所以明文“good night”相应的密文为$(64,67,67,25,0,59,11,64,3,9)$。
	}

 
	\begin{Exercise}
		设背包密码系统的超递增序列为$(3,4,8,17,35)$，乘数$t=17$，模数$k=67$，试对$25,2,72,92$解密。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为${{t}^{-1}}\bmod k={{17}^{-1}}\bmod 67=4\bmod 67$，则$4\times (25,2,72,92)\bmod 67=(33,8,20,33)$。
		所以其对应的明文分组为$(00001,00100,10010,00001)$，由课本120页表4-7可得明文为“ADRA”。
	}

 
	\begin{Exercise}
		已知$n=pq$，$p,q$都是素数，$x,y\in \mathbb{Z}_{n}^{*}$，其Jacobi符号都是$1$，其中$\mathbb{Z}_{n}^{*}={{\mathbb{Z}}_{n}}-\{0\}$\cite{yang-mcry}。证明：\\
		(1) $xy(\bmod n)$是模$n$的平方剩余，当且仅当$x,y$都是模$n$的平方剩余或$x,y$都是模$n$的非平方剩余。\\
		(2) ${{x}^{3}}{{y}^{5}}(\bmod n)$是模$n$的平方剩余，当且仅当$x,y$都是模$n$的平方剩余或$x,y$都是模$n$的非平方剩余。
		
	\end{Exercise}
	\jd{
		(1)必要性：\par
		若$xy(\bmod n)$是模$n$的平方剩余，即存在$t$使得$xy={{t}^{2}}\bmod n$，而$n=pq$，显然必有$xy={{t}^{2}}\bmod p,xy={{t}^{2}}\bmod q$，所以$xy$也同时是模$p$和模$q$的平方剩余，即$(\frac{xy}{p})=1,(\frac{xy}{q})=1\Rightarrow (\frac{x}{p})(\frac{y}{p})=1,(\frac{x}{q})(\frac{y}{q})=1$。
		又由题意得$(\frac{x}{n})=1,(\frac{y}{n})=1$，即$(\frac{x}{p})(\frac{x}{q})=1,(\frac{y}{p})(\frac{y}{q})=1$。所以：
		当$(\frac{x}{p})=1$时，有$(\frac{y}{p})=1\Rightarrow (\frac{y}{q})=1\Rightarrow (\frac{x}{q})=1$，即$x$同时是模$p$和模$q$的平方剩余，$y$也同时是模$p$和模$q$的平方剩余，即$x,y$都是模$n$的平方剩余；
		当$(\frac{x}{p})=-1$时，有$(\frac{y}{p})=-1\Rightarrow (\frac{y}{q})=-1\Rightarrow (\frac{x}{q})=-1$，即$x$同时是模$p$和模$q$的非平方剩余，$y$也同时是模$p$和模$q$的非平方剩余，即$x,y$都是模$n$的非平方剩余。
		充分性：\par
		若$x,y$都是模$n$的平方剩余，则$x,y$也是模$p$和模$q$的平方剩余，即\[(\frac{x}{p})=(\frac{x}{q})=(\frac{y}{p})=(\frac{y}{q})=1\]，即$xy$同时是模$p$和模$q$的平方剩余，所以$xy$是模$n$的平方剩余；
		若$x,y$都是模$n$的非平方剩余，则它们对于模$p$和模$q$至少有一种情况是非平方剩余，不妨设\[(\frac{x}{p})=-1,=(\frac{y}{p})=-1\]，则有\[(\frac{x}{q})=-1,(\frac{y}{q})=-1\]，即$x,y$也都是模$p$和模$q$的非平方剩余。所以\[(\frac{x}{p})(\frac{y}{p})=(\frac{xy}{p})=(-1)(-1)=1\]，同理\[(\frac{xy}{q})=1\]，即$xy$同时是模$p$和模$q$的平方剩余，所以$xy$是模$n$的平方剩余。
		\par
		
		(2)若${{x}^{3}}{{y}^{5}}(\bmod n)$是模$n$的平方剩余，则${{x}^{3}}{{y}^{5}}$同时是模$p$和模$q$的平方剩余，所以$\left( \frac{{{x}^{3}}{{y}^{5}}}{p} \right)=1={{(\frac{x}{p})}^{3}}{{(\frac{y}{p})}^{5}}$，由于勒让德符号的偶数次方肯定为$1$（$p|x$情况除外），即有\[1=(\frac{x}{p})(\frac{y}{p})\]，余下证明同(1)。\par
		提示：\\
		$ \left( \dfrac{xy}{n} \right)
		=\left( \dfrac{xy}{p} \right)\left( \dfrac{xy}{q} \right)
		=\left( \dfrac{x}{p} \right)\left( \dfrac{y}{q} \right)\left( \dfrac{x}{p} \right)\left( \dfrac{y}{q} \right)
		=\left( \dfrac{x}{p} \right)\left( \dfrac{x}{q} \right)\left( \dfrac{y}{p} \right)\left( \dfrac{y}{q} \right) \\ 
		\begin{matrix}
			{} & {} & =  \\
		\end{matrix}
		\left( \dfrac{x}{n} \right)\left( \dfrac{y}{n} \right)=1 \\ 
		$
		\par
		$\left(\dfrac{x^3 y^5}{n}\right)\\
		=\left(\dfrac{x^3 y^5}{p}\right) \left(\dfrac{x^3 y^5}{q}\right)\\
		=\left(\dfrac{x^3}{p}\right)\left(\dfrac{y^5}{q}\right)\left(\dfrac{x^3}{p}\right)\left(\dfrac{y^5}{q}\right)\\
		=\left(\dfrac{x^2}{p}\right) \left(\dfrac{x}{p}\right) \left(\dfrac{\left(y^2 \right)^2}{p}\right) \left(\dfrac{y}{p}\right) \left(\dfrac{x^2}{q}\right) \left(\dfrac{x}{q}\right) \left(\dfrac{\left( y^2 \right) ^2}{q}\right) \left(\dfrac{y}{q}\right)\\
		=\left(\dfrac{x}{p}\right) \left(\dfrac{x}{q}\right) \left(\dfrac{y}{p}\right) \left(\dfrac{y}{q}\right)\\
		=\left(\dfrac{x}{n}\right) \left(\dfrac{y}{n}\right)
		$
		
	}

 
	\begin{Exercise}
		在Rabin密码体制中设$p=53,q=59$： \\
		(1) 确定$1$在模$n$下的4个平方根。\\
		(2) 求明文消息$2347$所对应的密文。\\
		(3) 对上述密文，确定可能的4个明文。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)已知 $n=pq=53\times 59=3125$，由中国剩余定理可得到等价方程组：\par
		$\left\{ 
		 {{x}^{2}}\equiv 1\bmod 53 \\ 
		 {{x}^{2}}\equiv 1\bmod 59 \\ 
		 \right.$
		因为${{(\pm 1)}^{2}}\equiv 1\bmod 53{{(\pm 1)}^{2}}\equiv 1\bmod 59$，所以$x\equiv \pm 1\bmod 53x\equiv \pm 1\bmod 59$。经组合可得到以下四个方程组：\par
		$\left\{ 
		 x\equiv 1\bmod 53 \\ 
		 x\equiv 1\bmod 59 \\ 
		 \right.$	$\left\{ 
		 x\equiv 1\bmod 53 \\ 
		 x\equiv -1\bmod 59 \\ 
		 \right.$	$\left\{ 
		 x\equiv -1\bmod 53 \\ 
		 x\equiv 1\bmod 59 \\ 
		 \right.$	$\left\{ 
		 x\equiv -1\bmod 53 \\ 
		 x\equiv -1\bmod 59 \\ 
		 \right.$
		 \par
		根据中国剩余定理${{M}_{1}}=59,M_{1}^{-1}\bmod 53\equiv 9,{{M}_{2}}=53,M_{2}^{-1}\bmod 59\equiv 49$，则有：\\
		第一个方程组的解为$(59\cdot 9\cdot 1+53\cdot 49\cdot 1)\bmod 3127\equiv 1$；\\
		第二个方程组的解为$(59\cdot 9\cdot 1+53\cdot 49\cdot (-1))\bmod 3127\equiv 1061$；\\
		第三个方程组的解为$(59\cdot 9\cdot (-1)+53\cdot 49\cdot 1)\bmod 3127\equiv 2066$；\\
		第四个方程组的解为$(59\cdot 9\cdot (-1)+53\cdot 49\cdot (-1))\bmod 3127\equiv 3126$。\\
		所以，$1\bmod n$的四个平方根为$1\bmod n1061\bmod n2066\bmod n3126\bmod n$。\par
		
		(2)$2347$对应的密文为$c\equiv {{2347}^{2}}\bmod 3127\equiv 1762$。\par
		
		(3)解密即解${{x}^{2}}\equiv 1762\bmod 3127$，由中国剩余定理可得到等价方程组：\par
		$\left\{ 
		 {{x}^{2}}\equiv 1762\bmod 53=13 \\ 
		 {{x}^{2}}\equiv 1762\bmod 59=51 \\ 
		 \right.$
		 \par
		因为${{(\pm 15)}^{2}}\equiv 13\bmod 53{{(\pm 13)}^{2}}\equiv 51\bmod 59$，所以$x\equiv \pm 15\bmod 53,x\equiv \pm 13\bmod 59$，经组合可得到以下四个方程组：\par
		$\left\{ 
		 x\equiv 15\bmod 53 \\ 
		 x\equiv 13\bmod 59 \\ 
		 \right.$	$\left\{ 
		 x\equiv 15\bmod 53 \\ 
		 x\equiv -13\bmod 59 \\ 
		 \right.$ $\left\{ 
		 x\equiv -15\bmod 53 \\ 
		 x\equiv 13\bmod 59 \\ 
		 \right.$ $\left\{ 
		 x\equiv -15\bmod 53 \\ 
		 x\equiv -13\bmod 59 \\ 
		 \right.$
		 \par
		根据中国剩余定理${{M}_{1}}=59,{{M}_{1}}^{-1}\bmod 53\equiv 9,{{M}_{2}}=53,M_{2}^{-1}\bmod 59\equiv 49$，则有：\\
		第一个方程组的解为$(59\cdot 9\cdot 15+53\cdot 49\cdot 13)\bmod 3127\equiv 1075$；\\
		第二个方程组的解为$(59\cdot 9\cdot 15+53\cdot 49\cdot (-13))\bmod 3127\equiv 2347$；\\
		第三个方程组的解为$(59\cdot 9\cdot (-15)+53\cdot 49\cdot 13)\bmod 3127\equiv 780$；\\
		第四个方程组的解为$(59\cdot 9\cdot (-15)+53\cdot 49\cdot (-13))\bmod 3127\equiv 2052$。\\
		所以，四个可能的明文为$1075,2347,780,2052$。\
	}

 
	\begin{Exercise}
		椭圆曲线${{E}_{11}}(1,6)$表示${{y}^{2}}\equiv {{x}^{3}}+x+6\bmod 11$，求其上的所有点。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		模$11$的平方剩余有$1,4,9,5,3$。\\
		$x=1,4,6$时，${{y}^{2}}\equiv 8\bmod 11$，无解，曲线无与这一$x$相对应的点；\\
		$x=9$时，${{y}^{2}}\equiv 7\bmod 11$，无解，曲线无与这一$x$相对应的点；\\
		$x=0$时，${{y}^{2}}\equiv 6\bmod 11$，无解，曲线无与这一$x$相对应的点；\\
		$x=2$时，${{y}^{2}}\equiv 2\bmod 11,y=47$；\\
		$x=\text{3}$时，${{y}^{2}}\equiv 3\bmod 11,y=5\text{6}$；\\
		$x=\text{5}\text{7}\text{10}$时，${{y}^{2}}\equiv 4\bmod 11y=2\text{9}$；\\
		$x=\text{8}$时，${{y}^{2}}\equiv 9\bmod 11,y=3\text{8}$。\par
		所以椭圆曲线${{E}_{11}}(1,6)$上的所有点为：\\
		$\left\lbrace  (2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),O\right\rbrace $。
	}

 
	\begin{Exercise}
		已知点$G=(2,7)$在椭圆曲线${{E}_{11}}(1,6)$上，求$2G$和$3G$。\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)求$2G$。\\
		$
		 \lambda =\frac{3\times {{2}^{2}}+1}{2\times 7}\bmod 11=(13\times 4)\bmod 11=8\bmod 11, \\ 
		 {{x}_{2G}}=({{8}^{2}}-2-2)\bmod 11=5\bmod 11, \\ 
		 {{y}_{2G}}=[8\times (2-5)-7]\bmod 11=8\bmod 11, \\ 
		$\par
		所以$2G=(5,2)$。
		\par
		(2)易知$3G=2G+G=(5,2)+(2,7)$。\\
		$
		 \lambda =\frac{7-2}{5-2}\bmod 11=(5\times 7)\bmod 11=2\bmod 11, \\ 
		 {{x}_{3G}}=({{2}^{2}}-5-2)\bmod 11=8\bmod 11, \\ 
		 {{y}_{3G}}=[2\times (5-8)-2]\bmod 11=3\bmod 11, \\ 
		$
		\par
		所以$3G=(8,3)$。
	}


 
	\begin{Exercise}
		利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是${{E}_{11}}(1,6)$，生成元$G=(2,7)$，接收方A的秘密钥${{n}_{A}}=7$。\\
		(1) 求A的公开钥${{P}_{A}}$。\\
		(2) 发送方B欲发送消息${{P}_{m}}=(10,9)$，选择随机数$k=3$，求密文${{C}_{m}}$。\\
		(3) 显示接收方A从密文${{C}_{m}}$恢复消息${{P}_{m}}$的过程。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)易知公开钥${{P}_{A}}=7G=2\times 2G+3G$。\par
		$\bullet$求$2\times 2G$。\\
		$
		 \lambda =\frac{3\times {{5}^{2}}+1}{2\times 2}\bmod 11=(10\times 3)\bmod 11=8\bmod 11, \\ 
		 {{x}_{4G}}=({{8}^{2}}-5-5)\bmod 11=10\bmod 11, \\ 
		 {{y}_{4G}}=[8\times (5-10)-2]\bmod 11=2\bmod 11, \\ 
		$\par
		所以$2\times 2G=(10,2)$。
		\par
		$\bullet$由题19可得$3G=(8,3)$，即${{P}_{A}}=2\times 2G+3G=(10,2)+(8,3)$。\\
		$
		 \lambda =\frac{3-2}{8-10}\bmod 11=(1\times 5)\bmod 11=5\bmod 11, \\ 
		 {{x}_{7G}}=({{5}^{2}}-10-8)\bmod 11=7\bmod 11, \\ 
		 {{y}_{7G}}=[5\times (10-7)-2]\bmod 11=2\bmod 11, \\ 
		$\par
		所以${{P}_{A}}=(7,2)$。
		\par
		\par
		
		(2)密文${{C}_{m}}=(kG,{{P}_{m}}+k{{P}_{A}})$。
		$\bullet$求$kG$：$kG=3G=(8,3)$。
		\par
		$\bullet$求$k{{P}_{A}}$：$k{{P}_{A}}=2{{P}_{A}}+{{P}_{A}}=3G+7G=(2,7)+(7,2)$。
		$
		 \lambda =\frac{2-7}{7-2}\bmod 11=-1\bmod 11, \\ 
		 {{x}_{3{{P}_{A}}}}=({{(-1)}^{2}}-2-7)\bmod 11=3\bmod 11, \\ 
		 {{y}_{3{{P}_{A}}}}=((-1)\times (2-3)-7)\bmod 11=5\bmod 11, \\ 
		$
		所以$k{{P}_{A}}=(3,5)$。
		\par
		$\bullet$求${{P}_{m}}+k{{P}_{A}}$：${{P}_{m}}+k{{P}_{A}}=(10,9)+(3,5)$。
		$\
		 \lambda =\frac{5-9}{3-10}\bmod 11=-1\bmod 11, \\ 
		 {{x}_{{{P}_{m}}+k{{P}_{A}}}}=({{(-1)}^{2}}-10-3)\bmod 11=10\bmod 11, \\ 
		 {{y}_{{{P}_{m}}+k{{P}_{A}}}}=((-1)\times (10-10)-9)\bmod 11=2\bmod 11, \\ 
		$
		所以${{P}_{m}}+k{{P}_{A}}=(10,2)$。\par
		综上：${{C}_{m}}=(kG,{{P}_{m}}+k{{P}_{A}})=\{(8,3),(10,2)\}$。\par
		\par
		\par
		(3)从密文${{C}_{m}}$恢复消息${{P}_{m}}$的过程如下：\\
		$
		 {{P}_{m}}=({{P}_{m}}+k{{P}_{A}})-{{n}_{A}}(kG) \\ 
		 =(10,2)-7(8,3) \\ 
		 =(10,2)-(3,5) \\ 
		 =(10,2)+(3,6) \\ 
		 =(10,9). \\ 
		$\par
		其中：\\
		a)计算$7(8,3)$\\
		$\bullet$先计算$2(8,3)$。\\
		$
		 \lambda =\frac{3\times {{8}^{2}}+1}{2\times 3}\equiv 1\bmod 11, \\ 
		 {{x}_{2(8,3)}}={{1}^{2}}-8-8\equiv 7\bmod 11, \\ 
		 {{y}_{2(8,3)}}=1(8-7)-3\equiv 9\bmod 11, \\ 
		$\\
		所以$2(8,3)=(7,9)$。
		\\
		$\bullet$计算$3(8,3)=2(8,3)+(8,3)$。\\
		$
		 \lambda =\frac{3-9}{8-7}\equiv 5\bmod 11, \\ 
		 {{x}_{3(8,3)}}={{5}^{2}}-7-8\equiv 10\bmod 11, \\ 
		 {{y}_{3(8,3)}}=5(7-10)-9\equiv 9\bmod 11, \\ 
		$\\
		所以$3(8,3)=(10,9)$。
		\\
		$\bullet$计算$6(8,3)=3(8,3)+3(8,3)$。\\
		$
		 \lambda =\frac{3\times {{10}^{2}}+1}{2\times 9}=\frac{301}{18}\equiv 10\bmod 11, \\ 
		 {{x}_{6(8,3)}}={{10}^{2}}-10-10\equiv 3\bmod 11, \\ 
		 {{y}_{6(8,3)}}=10(10-3)-9\equiv 6\bmod 11, \\ 
		$\\
		所以$6(8,3)=(3,6)$。
		\\
		$\bullet$计算$7(8,3)=6(8,3)+(8,3)$。\\
		$
		 \lambda =\frac{3-6}{8-3}=\frac{-3}{5}\equiv 6\bmod 11, \\ 
		 {{x}_{7(8,3)}}={{6}^{2}}-3-8\equiv 3\bmod 11, \\ 
		 {{y}_{7(8,3)}}=6(3-3)-6\equiv 5\bmod 11, \\ 
		$\\
		所以$7(8,3)=(3,5)$。
		\\
		b)计算$\left( 10,2\right)-7\left( 8,3\right) = \left( 10,2\right)-\left( 3,5\right) =\left( 10,2\right)+\left( 3,-5\right) = \left( 10,2\right)+\left( 3,6\right) $ 。\\
		$
		 \lambda =\frac{6-2}{3-10}=\frac{4}{-7}\equiv 1\bmod 11, \\ 
		 x_{P_m}={{1}^{2}}-10-3\equiv 10\bmod 11, \\ 
		 {{y}_{{{P}_{m}}}}=1(10-10)-2\equiv 9\bmod 11, \\ 
		$\\
		所以$(10,2)-7(8,3)=(10,9)$。
		
	}

\chapter{密钥分配与管理}
	\begin{Exercise}
		
		\cite{mooc现代密码学聂旭云}
	\end{Exercise}
	\jd{
		
	}
	
	
	\begin{Exercise}
		在公钥体制中，每一用户U都有自己的公开钥$P{{K}_{U}}$和秘密钥$S{{K}_{U}}$。如果任意两个用户A,B按以下方式通信，A发给B消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),A \right)$，B收到后，自动向A返回消息$\left( {{E}_{P{{K}_{A}}}}\left( \text{m} \right),B \right)$，以使A知道B确实收到报文m。\\
		（1）问用户C怎样通过攻击手段获取报文m？\\
		（2）若通信格式变为：
		A发给B消息${{E}_{P{{K}_{B}}}}\left( {{E}_{S{{K}_{_{A}}}}}\left( m \right),m,A \right)$
		B向A返回消息${{E}_{P{{K}_{A}}}}\left( {{E}_{S{{K}_{_{B}}}}}\left( m \right),m,B \right)$
		这时的安全性如何？分析这时A、B如何相互认证并传递消息m。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)当A发给B消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),A \right)$时，A的身份“A”并没有认证，而B在收到消息后也无法对发送者进行检验，且身份A，B均明文传输，因此用户C可通过如下手段获得报文m：
		当A发给B消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),A \right)$时，C截取该消息并将身份A替换为自己的身份C，将修改后的消息$\left( {{E}_{P{{K}_{B}}}}\left( \text{m} \right),C \right)$发给接收者B；
		B提取消息后，根据身份“C”将返回消息$\left( {{E}_{P{{K}_{C}}}}\left( \text{m} \right),B \right)$；
		C再次劫取B返回的消息$\left( {{E}_{P{{K}_{C}}}}\left( \text{m} \right),B \right)$，用自己的私钥$S{{K}_{C}}$解密出消息m，并用A的公钥对m加密后将消息$\left( {{E}_{P{{K}_{A}}}}\left( \text{m} \right),B \right)$发给A。
		这样，用户C获得了报文m而没有影响A,B之间的正常通信，实现了攻击。
		\par
		
		(2)根据消息格式，先对消息m进行了签名，然后再进行加密，传送的消息具有了保密性和认证性，敌手无法获得报文明文，安全性提高。
		A，B之间相互认证传递消息的过程如下：
		B收到消息${{E}_{P{{K}_{B}}}}\left( {{E}_{S{{K}_{_{A}}}}}\left( m \right),m,A \right)$时，先用B自己的私钥解密得到消息$\left( {{E}_{S{{K}_{_{A}}}}}\left( m \right),m,A \right)$，然后根据提取的身份信息A，用A的公钥对消息m的签名${{E}_{S{{K}_{A}}}}\left( m \right)$的正确性进行验证，如果验证通过，则说明消息确实来自A。反之A用相同的方法可验证${{E}_{P{{K}_{A}}}}\left( {{E}_{S{{K}_{_{B}}}}}\left( m \right),m,B \right)$确实来自B，从而实现了相互认证。
	}

	\begin{Exercise}
		Diffie-Hellman密钥交换协议易受中间人攻击，即攻击者截获通信双方通信的内容后可分别冒充通信双方，以获得通信双方协商的密钥。详细分析攻击者如何实施攻击。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		虽然Diffie-Hellman密钥交换算法十分巧妙，但由于没有认证功能，存在中间人攻击。当Alice和Bob交换数据时，Trudy 拦截通信信息，并冒充Alice欺骗Bob，冒充Bob欺骗Alice。其过程如下：\\
		（1）Alice选取大的随机数x，并计算$X={{g}^{x}}\left( \bmod P \right)$，Alice将g、P、X传送给Bob，但被Trudy拦截；\\
		（2）Trudy冒充Alice选取大的随机数z，并计算$Z={{g}^{z}}\left( \bmod P \right)$，Trudy将Z传送给Bob；\\
		（3）Trudy冒充Bob，再将$Z={{g}^{z}}\left( \bmod P \right)$传送给Alice；\\
		（4）Bob选取大的随机数y，并计算$Y={{g}^{y}}\left( \bmod P \right)$，Bob将Y传送给Alice，但被Trudy拦截。\par
		由（1）、（3）Alice与 Trudy 共享了一个秘密密钥${{g}^{xz}}$，由（2）、（4）Trudy与Bob共享了一个秘密密钥${{g}^{yz}}$。
		以后在通信过程中，只要Trudy作中间人，Alice和 Bob不会发现通信的异常，但 Trudy可以获取所有通信内容。
		
	}

	\begin{Exercise}
		Diffie-Hellman密钥交换过程中，设大素数p=11，a=2是p的本原根.\\
		（1）用户A的公开钥${{Y}_{A}}\text{=}9$，求其秘密钥${{X}_{A}}$。\\
		（2）设用户B的公开钥${{Y}_{B}}=3$，求A和B的共享密钥K。		
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)${{X}_{A}}$满足${{Y}_{A}}={{a}^{{{X}_{A}}}}\bmod p$即$9\text{=}{{2}^{{{X}_{A}}}}\bmod 11$，所以有${{X}_{A}}$=6。\par
		(2)由Diffie-Hellman协议可知$K\text{=}Y_{B}^{{{X}_{A}}}\bmod p={{3}^{6}}\bmod 11=3$。
	}

	\begin{Exercise}
		线性同余算法${{X}_{\text{n+1}}}\text{=}\left( a{{X}_{n}} \right)\bmod {{2}^{4}}$，问：\\
		（1）该算法产生的数列的最大周期是多少？\\
		（2）a的值是多少？\\
		（3）对种子有何限制？
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)由于模$\text{m}={{2}^{4}}$因此它没有原根，又由递推式不难得知${{X}_{\text{n}}}\text{=}{{\text{a}}^{n}}{{X}_{0}}\bmod {{2}^{4}}$。因此该算法产生的序列的最大周期为$\text{a}\bmod {{2}^{4}}$的最大阶l，而$l|\varphi \left( {{2}^{4}} \right)$，但$l\ne \varphi \left( {{2}^{4}} \right)\text{=}8$。若l=4，则不难验证，${{X}_{0}}=1$，$a=3$时，数列周期为4，因此该算法产生数列的最大周期是4。
		\par
		(2)a必须满足$\gcd \left( a,{{2}^{4}} \right)=1$，所以a在$\left\{ 1,3,5,...,15 \right\}$中取值。
		周期为4的有$\left\{ 3,5,11,13 \right\}$，即为a的取值.		
		\par
		(3)种子${{X}_{0}}$必须满足$\gcd \left( {{X}_{0}},{{2}^{4}} \right)=1$。
	}

	\begin{Exercise}
		在Shamir秘密分割门限方案中，设k=3，n=5，q=17，5个子密钥分别是8、7、10、0、11，从中任选3个，构造插值多项式并求秘密数据s。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		取$f\left( 1 \right)=8$，$f\left( 2 \right)=7$，$f\left( 4 \right)=0$构造插值多项式:\\
		$
		 f\left( x \right)=8\left( x-2 \right)\left( x-4 \right)/\left( 1-2 \right)\left( 1-4 \right)+7\left( x-1 \right)\left( x-4 \right)/\left( 2-1 \right)\left( 2-4 \right)+0\left( x-1 \right)\left( x-2 \right)/\left( 4-1 \right)\left( 4-2 \right) \\ 
		 =8\left( x-2 \right)\left( x-4 \right)6+7\left( x-1 \right)\left( x-4 \right)8\bmod 17 \\ 
		 =2{{x}^{2}}+10x+13 \\ 
		$
		$s=f\left( 0 \right)=13$
		
	}

	\begin{Exercise}
		在基于中国剩余定理的秘密分割门限方案中，设$k=2$，$n=3$，${{m}_{1}}=7$，${{m}_{2}}=9$，${{m}_{3}}=11$，三个子秘钥分别是6、3、4，求秘密数据s。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		由题设可得s应满足$11={{m}_{3}}<s<{{m}_{1}}{{m}_{2}}=63$,
		因为$k=2，n=，{{m}_{1}}=7，{{m}_{2}}=9，{{m}_{3}}=11$，3个子密钥分别是6，3，4，那么:\\
		$
		M={{m}_{1}}\times {{m}_{2}}\times {{m}_{3}}\\
		=7\times 9\times 11\\
		=693 {{M}_{1}}\\
		=\frac{M}{{{m}_{1}}}
		=\frac{693}{7}=99$，\\
		
		${{N}_{1}}={{M}_{1}}^{-1}(\bmod {{m}_{1}})\\
		=9{{9}^{-1}}\bmod 7=1$\\
		
		${{M}_{2}}=\frac{M}{{{m}_{2}}}\\
		=\frac{693}{9}=77，\\
		{{N}_{2}}={{M}_{2}}^{-\text{1}}(\bmod {{m}_{2}})=7{{7}^{-1}}\bmod 9=2$\\
		
		${{M}_{3}}=\frac{M}{{{m}_{3}}}=\frac{693}{11}=63，{{N}_{3}}={{M}_{3}}^{-1}(\bmod {{m}_{3}})=6{{3}^{-1}}\bmod 11=7$
		\\
		由${{s}_{1}}=6，{{s}_{2}}=3$ 可得:\\
		$s={{s}_{1}}{{M}_{1}}{{N}_{1}}+{{s}_{2}}{{M}_{2}}{{N}_{2}}(\bmod 63)\\
		=6\times 99\times 1+3\times 77\times 2(\bmod 63)\\
		=1056(\bmod 63)\\
		=48$
		\\
		由${{s}_{2}}=3$，${{s}_{3}}=4$可得:\\
		$s={{s}_{2}}{{M}_{2}}{{N}_{2}}+{{s}_{3}}{{M}_{3}}{{N}_{3}}(\bmod 99)\\
		=3\times 77\times 2+4\times 63\times 7(\bmod 99)\\
		=2226(\bmod 99)\\
		=48$
		\\
		由${{s}_{1}}=6$，${{s}_{3}}=4$可得:\\
		$s={{s}_{1}}{{M}_{1}}{{N}_{1}}+{{s}_{3}}{{M}_{3}}{{N}_{3}}(\bmod 77)\\
		=6\times 99\times 1+4\times 63\times 7(\bmod 77)\\
		=2358(\bmod 77)\\
		=48$
		即秘密数据s为48.
	}

\chapter{消息认证和哈希函数}
	\begin{Exercise}
		消息认证能提供的安全属性有哪些？
	\end{Exercise}
	\jd{
	}

	\begin{Exercise}
		6.1.3节介绍的数据认证算法是由CBC模式的DES定义的，其中初始向量取为0，试说明使用CFB模式也可获得相同结果。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		6.1.3节用CBC模式的DES设计数据认证算法为：\\
		$
		O_1=E_K(D_1) \\
		O_2 = E_K(D_2 \oplus O_1)\\
		O_3 = E_K(D_3 \oplus O_2)\\
		\Rightarrow O_N=E_K(D_N \oplus E_K(D_{N-1}\oplus\ldots \oplus E_K(D_2 \oplus E_K(D_1))))\\
		\cdots
		O_N = E_K(D_N \oplus O_{N-1})
		$
		\par
		如果改用CFB模式来实现，由于输出为64位，所以必须取$j=64$ ，也就是每次移位寄存器左移整个64位。为了达到相同的结果，可取CFB模式中$IV=D_1,P_i=D_{i+1},P_N=0 \left( i=1,\ldots,N-1 \right) $ ，则有：\\
		$
		O_1=D_2 \oplus E_K(D_1) \\
		O_2 = D_3 \oplus E_K( O_1)\\
		O_3 = D_4 \oplus E_K( O_2)\\
		\Rightarrow O_N=E_K(O_{N-1})=E_K(D_N \oplus E_K(D_{N-1}\oplus\ldots \oplus E_K(D_2 \oplus E_K(D_1))))\\
		\cdots
		O_{N-1} = D_N \oplus E_K(O_{N-2})\\
		O_N = 0 \oplus E_K(O_{N-1})
		$
		比较两式， $O_N$作为消息认证码，结果相同。
		
	}

	
	\begin{Exercise}
		什么是哈希函数的抗强碰撞性？抗弱碰撞性？单向性？
	\end{Exercise}
	\jd{找到任意两个不同输入$y,x,y \neq x$,满足$h(y)=h(x)$在计算上是不可行的，称为此哈希函数具有抗强碰撞性。\par
		已知x，找到$y,y \neq x,$满足$h(y)=h(x)$，在计算上是不可行的，称为此哈希函数具有抗弱碰撞性。\par
		已知y，找到x满足$y=h(x)$在计算上不可行，称为哈希函数的单向性。
	}

	\begin{Exercise}
		以下Hash函数的输入分组长度和输出数据长度分别为多少。\par
		\begin{enumerate}
			\item SHA1
		\end{enumerate}
	\end{Exercise}
	\jd{
		\begin{enumerate}
			\item SHA1:输入512bits，输出160bits。
		\end{enumerate}
	}

	\begin{Exercise}
		有很多哈希函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将消息M分成分组$M_1, M_2,…,M_N，H_0=$初值，迭代关系为 $H_i=E_{M_i}\left( H_{i-1}\right) \oplus H_{i-1}\left( i=1,2,…,N\right) $,哈希值取为$H_N$，其中E是分组加密算法。\\
		（1）设E为DES，第3章的习题已证明如果对明文分组和加密密钥都逐比特取补，那么得到的密文也
		是原密文的逐比特取补，即如果$Y=DES_K\left( X\right) $，那么$Y’=DES_{K’}\left( X’\right) $。利用这一结论证明在上述哈希函数中可对消息进行修改但却保持哈希值不变。\\
		（2）若迭代关系$H_i=E_{H_{i-1}} \left(M_i \right) \oplus M_i$ ，证明仍可对其进行上述攻击。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)敌手主要是通过修改函数的输入值 $M_1,M-2,\ldots,M_N$和 来构造碰撞。\par
		$
		H_1=DES_{M_1}\left(H_0 \right) \oplus H_0\\
		H_2=DES_{M_2}\left(H_1 \right) \oplus H_1\\
		\ldots \\
		H_N=DES_{M_N}\left(H_N \right) \oplus H_{N-1}\\
		$
		\par
		利用 $Y'=DES_{K'}\left( X'\right) $和$X' \oplus Y'=X\oplus Y$ 两个性质可知，若敌手同时对 $M_1$和 $M_0$逐比特取补，则由性质一知$DES_{M_1}\left( H_0\right) $ 也被逐比特求补，由性质二知$H_1$ 保持不变，所以$H_2,\ldots,H_N$ 也都不受影响，所以有： $H\left( M_1 M_2\ldots M_N\right) =H\left( M_1^{'} M_2 \ldots M_N\right)=H_N $
		\par
		(2)改迭代关系为$H_i=E_{H_{i-1}} \left(M_i \right) \oplus M_i$ ，则敌手也可同时对 $M_1$和 $H_0$逐比特取补，由性质一知 $DES_{H_0}\left( M_1\right) $也被逐比特求补，由性质二知 $H_1,\ldots,H_N$都不受影响，故仍可进行上述攻击。
		
	}

	\begin{Exercise}
		考虑用公钥加密算法构造哈希函数，设算法是RSA，将消息分组后用公开钥加密第一个分组，加密结果与第二个分组异或后，再对其加密，一直进行下去。设一消息被分成两个分组B1和B2，其哈希值为
		$H\left( B_1, B_2\right) =RSA\left( RSA\left( B_1\right) \oplus B_2\right) $。证明对任一分组$C_1$可选$C_2$，使得$H\left( C_1, C_2\right) = H\left( B_1, B_2\right) $。证明用这种攻击法，可攻击上述用公钥加密算法构造的哈希函数。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		对任一分组$C_1$ ，可构造$C_2$ 如下：\\
		$C_2=RSA\left( C_1\right) \oplus RSA\left(B_1 \right) \oplus B_2 $\\
		则:\\
		$H\left(C_1,C_2 \right) \\
		=RSA\left( RSA\left( C_1\right) \oplus C_2 \right) \\
		=RSA\left( RSA\left( C_1\right) \oplus RSA\left( C_1\right) \oplus RSA\left( B_1\right) \oplus B_2 \right)\\
		=RSA\left( RSA\left( B_1\right) \oplus B_2 \right)\\
		=H\left( B_1,B_2\right) 
		$
		设哈希函数的输入消息分组为 $M_1,M_2,\ldots,M_N$，则可任取$M_1^{'}$ 替代$M_1$ ，并由上述方法构造$M_2^{'}$ 替代$M_2$ ，可得$H\left( M_1^{'},M_2^{'},\ldots,M_N\right) = H\left( M_1,M_2,\ldots,M_N\right)$ ，攻击成功。
		
	}

	\begin{Exercise}
		在图6-11中，假定有80个32比特长的字用于存储每一个$W_t$，因此在处理信息分组前，可预先计算出这80个值。为节省存储空间，考虑有16个字的循环移位寄存器，其初值存储前16个值（即$W_0，W_1，…, W_{15}$），设计一个算法计算以后的每一个$W_t$。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		 $W_0\sim W_{15}$为消息分组的16个字，初始放在移位寄存器中，如图\ref{fig1}连接电路。$CLS_1$ 的输出反馈到移位寄存器右边的输入端，则每个时钟到来时，移位寄存器从左边输出端移出一个字
		 $W_i\left( i=0,\ldots ,79\right) $ 。\par
		 
	}
	\begin{figure}[h]
		\centering
		\includegraphics[width=\linewidth] {ex6-4.png}
		\caption{移位寄存器连接图}
		\label{fig1}
	\end{figure}

	\begin{Exercise}
		对SHA，计算$W_{16}，W_{17}，W_{18}，W_{19}$.
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		\begin{equation}
			W_{16} = CLS_1 \left( W_0 \oplus W_2 \oplus W_8 \oplus W_{13} \right) \\
			W_{17} = CLS_1 \left( W_1 \oplus W_3 \oplus W_9 \oplus W_{14} \right) \\
			W_{18} = CLS_1 \left( W_2 \oplus W_4 \oplus W_{10} \oplus W_{15} \right) \\
			W_{19} = CLS_1 \left( W_3 \oplus W_5 \oplus W_{11} \oplus W_{16} \right) \\
		\end{equation}
	}

	\begin{Exercise}
		设$a_1 a_2 a_3 a_4$是32比特长的字中的4个字节，每一给$a_i$可看作由二进制表示的0~255之间的整数，在大端方式中，该字表示整数$a_1 2^{24}+a_2 2^{16}+a_3 2^8+a_4$，在小端结构中，该字表示整数$a_4 2^{24}+a_3 2^{16}+a_2 2^8+a_1$。
		\cite{yang-mcry}\\
		（1）MD5使用小端结构，因消息的摘要值不应依赖于算法所用的结构，因此在MD5中为了对以大端
		方式存储的两个字$X=x_1 x_2 x_3 x_4$和$Y=y_1 y_2 y_3 y_4$进行模2加法运算，必须要对这两个字进行调整，问如何进行？\\
		（2）SHA使用大端方式，问如何对以小端结构存储的两个字X和Y进行模2加法运算。
		
	\end{Exercise}
	\jd{
		(1)由于MD5使用little-endian结构，而X，Y使用的是big-endian存储结构，因此必须把X，Y转换成little-endian格式，则有:\\
		$
		x_1 2^{24} + x_2 2^{16} + x_3 2^{8} +x_4 
		=x_4^{'} 2^{24} + x_3^{'} 2^{16} + x_2^{'} 2^{8} + x_1^{'}\\
		\Rightarrow x_1^{'}=x_4,x_2^{'}=x_3,x_3^{'}=x_2,x_4^{'}=x_1
		$
		\par
		
		(2)由于SHA使用big-endian结构，而X，Y使用的是little-endian存储结构，因此必须把X，Y转换
		成big-endian格式，则有:\\
		$
		x_4 2^{24} + x_3 2^{16} + x_2 2^{8} +x_1 
		=x_1^{'} 2^{24} + x_2^{'} 2^{16} + x_3^{'} 2^{8} + x_4^{'}\\
		\Rightarrow x_1^{'}=x_4,x_2^{'}=x_3,x_3^{'}=x_2,x_4^{'}=x_1
		$	
		
	}

\chapter{数字签名}
	\begin{Exercise}
		数字签名能提供的安全属性有哪些？
	\end{Exercise}
	\jd{
	}

	\begin{Exercise}
		在DSS数字签名标准中，$p=83=2\times 41+1,q=41,h=2$，于是$g\equiv {{2}^{2}}\equiv 4\bmod 83$，若取$x=57$，则$y\equiv {{g}^{x}}\equiv {{4}^{57}}=77\bmod 83$。在对消息$M=56$签名时，选择$k=23$，计算签名并进行验证。
		\cite{yang-mcry}\\
	\end{Exercise}
	\jd{
		(1)签名过程：为了简化，用$M$代替$H(M)$，则用户对消息$M$的签名为$(r,s)$。计算:
		\[r=({{g}^{k}}\bmod p)\bmod q=({{4}^{23}}\bmod 83)\bmod 41=51\bmod 41=10 \]
		\[{{k}^{-1}}\bmod q={{23}^{-1}}\bmod 41=25\]
		\[s=[{{k}^{-1}}(M+xr)]\bmod q=[25\times (56+57\times 10)]\bmod 41=29 \]
		所以签名$(r,s)=(10,29)$。
		\par
		
		(2)验证过程：接收方收到的消息为$M'$，签名为$(r',s')=(10,29)$。计算:\\
		$w={{({s}')}^{-1}}\bmod q={{29}^{-1}}\bmod 41=17$，\\
		${{u}_{1}}=(M'w)\bmod q=(56\times 17)\bmod 41=9$，\\
		${{u}_{2}}=(r'w)\bmod q=(10\times 17)\bmod 41=6$，\\
		$v=[({{g}^{{{u}_{1}}}}{{y}^{{{u}_{2}}}})\bmod p]\bmod q=[({{4}^{9}}\times {{77}^{6}})\bmod 83]\bmod 41=10$。\\
		因为$v=r'=10$，所以认为签名有效，即验证通过。
	}

	\begin{Exercise}
		在DSA签名算法中，参数$k$泄露会产生什么后果？
		\cite{yang-mcry}\\
	\end{Exercise}
	\jd{
		若攻击者得到了一个有效签名$(r,s)$，并且知道了DSA签名算法中的参数$k$，那么在签名方程$s=[{{k}^{-1}}(H(M)+xr)]\bmod q$中只存在一个未知数，即用户的秘密钥$x$，所以攻击者可以求得秘密钥$x=[(ks-H(M)){{r}^{-1}}]\bmod q$。因此，参数$k$泄漏将导致签名秘密钥的泄漏，攻击者可以伪造任意消息的签名。
	}

\chapter{认证协议}
	\begin{Exercise}
		假设你知道一个背包问题的解，试设计一个协议，以零知识证明方式证明你的确知道问题的解。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{解一：\par
		设背包向量为$A$，证明者P知道一个背包容积x的解${{B}_{x}}$，即$A{{B}_{x}}=x$，P以零知识证明方式向验证者证明自己掌握秘密${{B}_{x}}$的协议如下：\\
		\textcircled{1} P随机选取一向量${{B}_{y}}$，计算$A{{B}_{y}}=y$，将y发给V。\\
		\textcircled{2} V随机选$e\in \left\{ 0,1 \right\}$，将$e$发给P；\\
		\textcircled{3}  P计算$C={{B}_{y}}+e{{B}_{x}}$，即$e=0$时，$C={{B}_{y}}$；$e=1$时，$C={{B}_{y}}+{{B}_{x}}$，将$C$发给V。\\
		注：如果$e=0$，P展示$y$的解，即${{B}_{y}}$；如果$e=1$，P展示被加密的$y$的解，即${{B}_{y}}+{{B}_{x}}$。\\
		\textcircled{4} 若$AC=y+ex$，V接受P的证明。\par
		
		协议的完备性、正确性和安全性:\\
		(1) 完备性：如果P和V遵守协议，且P知道$x$的解${{B}_{x}}$，则应答$C$使得$AC=y+ex$，V接受P的证明。\\
		(2) 正确性：假冒的证明者E可按以下方式以$\frac{1}{2}$的概率骗得V接受自己的证明：\\
		\textcircled{1} E随机选取一向量${{B}_{y}}$和$\tilde{e}\in \left\{ 0,1 \right\}$，计算$A{{B}_{y}}=y$，将$y-\tilde{e}x$发给V。\\
		\textcircled{2} V随机选$e\in \left\{ 0,1 \right\}$，将$e$发给E；\\
		\textcircled{3} E将${{B}_{y}}$发给V。\\
		V的验证方程为$A{{B}_{y}}=y-\tilde{e}x+ex$。当$\tilde{e}=e$时，方程成立，V接受E的证明，E欺骗成功。因$\tilde{e}=e$的概率是$\frac{1}{2}$，所以E成功的概率是$\frac{1}{2}$。\\
		
		另一方面，$\frac{1}{2}$是E成功的最好概率，否则假定E以大于$\frac{1}{2}$的概率使V相信自己的证明，那么E知道一个$y$，对这个$y$，他可以正确回答V的两个询问$e=0$和$e=1$，意味着E能计算$A{{C}_{1}}=yA{{C}_{2}}=y+x$，由此可计算$x=A({{C}_{2}}-{{C}_{1}})$，因此得秘密${{B}_{x}}=({{C}_{2}}-{{C}_{1}})$。\\
		
		(3) 安全性：根据以上的讨论知，假冒的证明者E欺骗V成功的概率为$\frac{1}{2}$，这个概率太大了。为减少这个概率，可以将协议重复执行多次，设执行t次，则欺骗成功的概率将减少到${{2}^{-t}}$。
		\par
		解二：\par
		(1)构造背包问题\par
		先选大素数$N，g，1<g<N$，N是素数，且$\left( N-1 \right)/2$ 也为素数，g为N的本原根。P随机选取t个整数${{S}_{1}},{{S}_{2}},\ldots,{{S}_{t}}$ (不用超递增序列)，计算
		\[{{V}_{1}}={{g}^{{{s}_{1}}}}\bmod N\]
		\[{{V}_{2}}={{g}^{{{s}_{2}}}}\bmod N\]
		\[ \ldots \]
		\[{{V}_{t}}={{g}^{{{s}_{t}}}}\bmod N\]
		式中${{S}_{1}}，{{S}_{2}}，\ldots，{{S}_{t}}$为秘密密钥；$N，g,{{V}_{1}},{{V}_{2}},\ldots,{{V}_{t}}$ 为公开。
		\par
		
		(2)零知识证明协议\\
		1)P随机选择r，计算 $x={{g}^{r}}\bmod N$，并将x传送给V；\\
		2)V随机选择t个二进制比特序列${{b}_{1}},{{b}_{2}},\ldots,{{b}_{t}}$，并将其传送给P；\\
		3)P计算$M=\sum\limits_{i=1}^{t}{{{b}_{i}}}{{S}_{i}},y=M+r$，并将其传送给V。\\
		4)V验证，计算
		\[{{Z}_{i}}=\{_{1,{{b}_{i}}=0}^{{{V}_{i}},{{b}_{i}}=1} \quad i=1,2,\ldots ,t\]
		\[y'=x{{Z}_{1}}{{Z}_{2}}\ldots {{Z}_{t}}\]
		比较$y=y'$是否成立，若成立，说明P了解秘密密钥${{S}_{1}},{{S}_{2}},\ldots,{{S}_{t}}$；反之，P为假冒。
		\par
		(3)安全性\par
		此类算法的安全威胁主要来自P欺骗V或V假冒P。假如使用的背包和离散对数没有问题，P欺骗V和V假冒P成功的概率都基于${{b}_{i}}\left( 1\le i\le t\right) $ 的随机性，若每一个${{b}_{i}}\left( 1\le i\le t\right) $的选取为0或1的概率为$\dfrac{1}{2}$，则假冒或欺骗成功的几率为$\dfrac{1}{2^t}$；若该协议重复k次，成功的几率为$\dfrac{1}{2^{tk}}$。
	}

	\begin{Exercise}
		在8.1.4节，基于大数分解问题的“多传一”不经意传输协议中为什么要求${{p}_{j}}\equiv {{q}_{j}}\equiv 3\bmod 4$？设${{n}_{j}}=55=5\times 11$，B选择${{x}_{j}}=2$，且想获得A的秘密${{s}_{j}}$，分析B是否能成功获得。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1) 要求${{p}_{j}}\equiv {{q}_{j}}\equiv 3\bmod 4$是为了保证同一数$a$在模${{n}_{j}}={{p}_{j}}{{q}_{j}}$下的两个平方根有相反的Jacobi符号。\par
		(2) B先计算Jacobi符号$\left( \frac{{{x}_{j}}}{{{n}_{j}}} \right)$和$x_{j}^{2}\bmod {{n}_{j}},\left( \frac{2}{55} \right)=1,\ {{2}^{2}}\equiv \bmod 55=4$，将(4,-1)发给A。\par
		接下来A计算4 mod55的平方根，求出4在mod 5时的平方根为$\pm 2,4$在mod11时的平方根为$\pm 2$，可得以下四个方程组：\\
		$\left\{ \begin{matrix}
			x\equiv 2\bmod 5 \\ 
			x\equiv 2\bmod 11 \\ 
		\end{matrix}\right.$
		 
		    
		 $\left\{ \begin{matrix} 
		 x\equiv 2\bmod 5 \\ 
		 x\equiv -2\bmod 11 \\ 
		 \end{matrix}\right.$
		   
		 $\left\{ \begin{matrix} 
		 x\equiv -2\bmod 5 \\ 
		 x\equiv 2\bmod 11 \\ 
		\end{matrix}\right.$
		
		$\left\{ \begin{matrix}
		 x\equiv -2\bmod 5 \\ 
		 x\equiv -2\bmod 11 \\ 
		 \end{matrix}\right.$
		 \par
		由${{M}_{1}}=11M_{1\grave{\ }}^{-1}\bmod 5\equiv 1{{M}_{2}}=5M_{2}^{-1}\bmod 11\equiv 9$\\
		第一个方程组的解为:\[\left( 2\times 11\times 1+2\times 5\times 9 \right)\bmod 55\equiv 2\]
		第二个方程组的解为:\[\left( 2\times 11\times 1-2\times 5\times 9 \right)\bmod 55\equiv 42\]
		第三个方程组的解为:\[\left( -2\times 11\times 1+2\times 5\times 9 \right)\bmod 55\equiv 13\]
		第四个方程组的解为:\[\left( -2\times 11\times 1-2\times 5\times 9 \right)\bmod 55\equiv 53\]
		因\[\left( \frac{2}{55} \right)=\left( \frac{13}{55} \right)=1\quad \left( \frac{42}{55} \right)=\left( \frac{53}{55} \right)=-1\]，A将42或53发给B。\par
		当A将42发给B时，B由$\gcd (55\ 42+2)=11$得到n的一个因子，从而得到n的分解式$11\times 5$，从而获得A的秘密${{s}_{j}}$。\par
		当A将53发给B时，因$53\equiv 2\bmod 55$,所以B不能计算出n的一个因子，没有得到任何新信息，从而不能获得A的秘密${{s}_{j}}$。
		
	}
	
	\begin{Exercise}
		设$p$是素数，群$Z_{p}^{*}$的元素$g$是群$Z_{p}^{*}$的生成元，当且仅当对每一$h\in Z_{p}^{*}$，存在一整数$x$，使得$h\equiv {{g}^{x}}\bmod p$。\\
		(1) 在$Z_{p}^{*}$中均匀、随机选取一元素$h$，证明，如果$g$不是$Z_{p}^{*}$的生成元，则存在一整数$x$，使得$h\equiv {{g}^{x}}\bmod p$成立的概率至多是$\frac{1}{2}$。\\
		(2) 给出$g$是$Z_{p}^{*}$的生成元的零知识证明。\\
		(3) 在(2)中的零知识证明中，证明者能否在多项式时间内完成证明，为什么？		
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1) 因为$g$不是$Z_{p}^{*}$的生成元，记循环群$\left\langle g \right\rangle $为$H$，显然$H$是$Z_{p}^{*}$的子群，且$\left| H \right|\left| \left| Z_{p}^{*} \right| \right.$，设$\frac{\left| Z_{p}^{*} \right|}{\left| H \right|}=r$，$r$是一个大于1的正整数，所以
		$
		\dfrac{\left| H \right| }{\left| Z_p^* \right| }=\dfrac{1}{r} \leq \dfrac{1}{2}
		$
		 。\par
		在$Z_{p}^{*}$中均匀、随机选取一元素$h$，若$h\in H$，则可在$H$上找到一个$x$，使得$h\equiv {{g}^{x}}\bmod p$成立。而$h\in H$的概率至多是$\frac{1}{2}$，所以$h\equiv {{g}^{x}}\bmod p$成立的概率至多是$\frac{1}{2}$。
		\par
		
		(2) \textcircled{1} V在$Z_{p}^{*}$中任意取一个元素$h$，发送给P。\par
		\textcircled{2} P知道$x$，使得$h\equiv {{g}^{x}}\bmod p$。P在$Z_{p}^{*}$中随机取一个元素$k$，计算${{h}_{1}}\equiv {{g}^{k}}\bmod p$并发送给V。\par
		\textcircled{3}	V随机选$e\in \left\{ 0,1 \right\}$，将$e$发给P；\par
		\textcircled{4}	P计算$b=k+ex$并发送给V。\par
		\textcircled{5}	V验证${{g}^{b}}={{h}_{1}}{{h}^{e}}$，若成立，则接受P的证明。\par
		\textcircled{6}	P和V重复以上过程$n$次。\par
	
		(3) 以上的证明可以在多项式时间内完成。因为，$n$是一个有限值，${{h}_{1}}\equiv {{g}^{k}}\bmod p$可以在多项式时间内完成。
	}

	\begin{Exercise}
		设n是两个未知大素数p和q的乘积，$x_0,x_1\in  Z_n^*$ 且其中至少一个是模n的二次剩余。又设$x_0,x_1$模n的Jacobi符号都为1，考虑下面交互证明系统，其中$x_0,x_1$和n作为输入，P为证明者，V为验证者：\cite{yang-mcry}\\
		\textcircled{1} P随机选择$i\leftarrow _R \{0,1\},v_b,v_(1-b) \leftarrow _R Z_n^*$，计算$y_b\equiv v_b^2  mod n$及$y_(1-b)\equiv v_(1-b)^2 (x_(1-b)^i )^(-1)  mod n$，将$y_0,y_1$发送给V。\\
		\textcircled{2} V随机选择$c\leftarrow _R \{0,1\}$，将c发送给P。\\
		\textcircled{3} P计算$z_b\equiv u^(i\oplus c) v_b mod n,z_(1-b)\equiv v_(1-b)$，将$z_b,z_1$发送给V。\\
		\textcircled{4} V检查$z_0^2\equiv y_0  mod n$和$z_1^2\equiv x_1^c y_1  mod n$是否成立，或$z_0^2\equiv x_0 y_0  mod n$和$z_1^2\equiv x_1^(1-c) y_(1 ) mod n$是否成立。如果不成立，则拒绝并终止。
		\par
		以上过程重复$log_2 (v)$次。\\
		(1)证明以上协议证明了$x_0,x_1$中至少有一个是模n的二次剩余。\\
		(2)证明以上协议是完备的.
		
	\end{Exercise}
	\jd{
		(1)对于给定的$y_0,y_1$ 和$x_0,x_1$,证明者P都能够回答c=0或c=1的两个挑战；
		故说明$y_0$ 和$y_0x_0$都是模n的二次剩余或者$y_1 $和$y_1 x_1$都是模n的二次剩余；
		根据数论知识可得：$x_0 $或$x_1$至少有一个是模n的二次剩余。
		\par
		(2)若Prover和Verifier都是诚实的，且(1)是正确的，显然，验证者最终会接受证明者的证明。
	}

\chapter{可证明安全}
	\begin{Exercise}
		解释语义安全的概念，这一概念可用于抵抗如下攻击吗？\\
		1）被动的多项式时间有界敌手；\\
		2）被动的多项式时间无界敌手；\\
		3）主动的多项式时间有界敌手。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		语义安全：一个安全的加密方案应使敌手通过密文得不到任何信息，即使是1比特的信息。
		此概念可用于抵抗被动的多项式时间有界敌手和主动的多项式有界敌手，但不能抵抗被动的多项式无界敌手。
		
	}

	\begin{Exercise}
		Rabin密码体制是IND-CPA安全的吗？是IND-CCA安全的吗？是IND-CCA2安全的吗？
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		Rabin密码体制Rabin密码体制是RSA密码体制的一种修正，假定模数$n=pq$ 不能被分解，该类体制对于选择明文攻击是计算安全的。因此，Rabin密码体制提供了一个可证明安全的密码体制的例子：假定分解整数问题是整数上不可行的，那么Rabin密码体制是安全的。\par
		
		Rabin密码体制：\par
		(一)	密钥生成\\
		设$n=pq$，其中p和q是素数，且$p\equiv q\equiv 3(mod4)$，即这两个素数形式为$4k+3$，计算$n=pq$。
		n为公钥，p,q为私钥。
		\par
		(二)	加密\\
		$c\equiv {{m}^{2}}\bmod n$
		,其中m是明文分组，c是对应的密文分组。
		\par
		(三)	解密\\
		解密也就是求c模n的平方根，即解${{x}^{2}}\equiv c\bmod n$，该方程等价于方程组：
		\[\begin{matrix}
		{{x}^{2}}\equiv c\bmod p  \\
		{{x}^{2}}\equiv c\bmod q  \\
		\end{matrix}\]
		由于$p\equiv q\equiv 3(mod4)$，所以可以解出每个方程有两个解：
		\[\begin{matrix}
		x\equiv y\bmod p,x\equiv -y\bmod p  \\
		x\equiv z\bmod q,x\equiv -z\bmod q  \\
		\end{matrix}\]
		两两组合可得4个同余方程组：
		\[\begin{matrix}
		x\equiv y\bmod p  \\
		x\equiv z\bmod q  \\
		\end{matrix}\]
		\[\begin{matrix}
		x\equiv y\bmod p  \\
		x\equiv -z\bmod q  \\
		\end{matrix}\]
		\[\begin{matrix}
		x\equiv -y\bmod p  \\
		x\equiv z\bmod q  \\
		\end{matrix}\]
		\[\begin{matrix}
		x\equiv -y\bmod p  \\
		x\equiv -z\bmod q  \\
		\end{matrix}\]
		由中国剩余定理可解出每一个方程组的解，共四个，即每一密文对应的明文不唯一。
		为有效确定明文一般在m 中加入某些代表性信息，如：发送者身份号、接受者身份号、时间、日期等。
		\par
		下面证明，当$p\equiv q\equiv 3(mod4)$时，两个方程${{x}^{2}}\equiv c\bmod p$，${{x}^{2}}\equiv c\bmod q$的平方根都很容易求出。
		\par
		由$p\equiv 3(mod4)$得，$p+1=4k$，即$\frac{1}{4}\left( p+1 \right)$是一个整数。因c是模p的平方剩余，故$\left( \frac{c}{p} \right)\equiv {{c}^{(p-1)/2}}\equiv 1\bmod p$.\par
		设${{x}^{2}}\equiv c\bmod p$的根为y，即${{y}^{2}}\equiv c\bmod p$，则
		\[{{\left( {{c}^{\frac{p+1}{4}}} \right)}^{2}}\equiv {{\left( {{y}^{\frac{p+1}{2}}} \right)}^{2}}\equiv {{\left( {{y}^{2}} \right)}^{\frac{p+1}{2}}}\equiv {{c}^{\frac{p+1}{2}}}\equiv {{c}^{(p-1)/2}}\cdot c\equiv c\bmod p\]
		所以${{c}^{\frac{p+1}{4}}}$和$p-{{c}^{\frac{p+1}{4}}}$是方程\[{{x}^{2}}\equiv c\bmod p\]的两个根。
		同理，${{c}^{\frac{p+1}{4}}}$和$q-{{c}^{\frac{p+1}{4}}}$是方程\[{{x}^{2}}\equiv c\bmod q\]的两个根。
		\par
		当$p\equiv q\equiv 3(mod4)$时，求解方程${{x}^{2}}\equiv a\bmod n$与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。\par
		所以Rabin密码体制对选择明文攻击是可证明安全的，然而该体制对选择密文攻击是完全不安全的，因预言机(orcale?)用实际解密算法来代替，就可以攻破密码体制。\par
		
		所以Rabin密码体制是IND-CPA安全的，但不是IND-CCA安全的，也不是IND-CCA2安全的。
		
	}

	\begin{Exercise}
		计算性Diffie-Hellman问题（Computational Diffie-Hellman,CDH问题）是已知$g,{{\text{g}}^{x}},{{g}^{y}}$，计算${{\text{g}}^{xy}}$。离散对数问题（Discrete Logarithm问题，DL问题）是已知$g,{{\text{g}}^{x}}$，计算x。证明如下关系\cite{yang-mcry}：
		\[DL\Leftarrow CDH\Leftarrow DDH\]
	\end{Exercise}
	\jd{
		1）证明$CDH\Leftarrow DDH$\par
		定义DDH假设: 设G是阶为大素数q的群，g为G的生成元。则以下两个分布：
		随机四元组\[R=(g,{{g}^{x}},{{g}^{y}},{{g}^{z}})\in {{G}^{4}}\]
		四元组\[D=(g,{{g}^{x}},{{g}^{y}},{{g}^{xy}})\in {{G}^{4}}\]
		（称为Diffie-Hellman四元组，简称DH四元组）。是计算上不可区分的，称为DDH假设。\par
		具体地说，对任一敌手$\mathcal{A}$，$\mathcal{A}$区分R和R的优势是$\varepsilon $可忽略的。\par
		设${{\mathcal{R}}_{DH}}$是R构成的集合，${{\mathcal{D}}_{DH}}$是D构成的集合,
		下面构造一个敌手$\mathcal{B}$，$\mathcal{B}$利用$\mathcal{A}$来攻击CDH问题。\par
		设$x,y\leftarrow {}_{R}{{Z}_{q}},t\in G,g\in G$,
		$\mathcal{B}$输入四元组$T=g,{{\text{g}}^{x}},{{g}^{y}},t$,目标是判断$T\in {{\mathcal{R}}_{DH}}$还是		
		\[ T\in {{\mathcal{D}}_{DH}} \]
		\[T\leftarrow \mathcal{B}\]
		\[\beta \in \left\{ 0,1 \right\}\]
		\[\beta \leftarrow \mathcal{A}\]
		如果$\beta =1$则说明$T\in {{\mathcal{D}}_{DH}}$，输出${{g}^{xy}}=t$；\\
		否则$\beta =\text{0}$则说明$T\in {{\mathcal{R}}_{DH}}$，终止。\\
		此时$\mathcal{B}$选中t的概率是$\frac{1}{q}$，故$\mathcal{B}$获胜的概率是$\frac{\varepsilon }{q}$.
		\par
		2）证明$DL\Leftarrow CDH$\par
		由CDH问题可知，对任一敌手$\mathcal{A}$，在已知$g,{{\text{g}}^{x}},{{g}^{y}}$情况下，$\mathcal{A}$计算${{\text{g}}^{xy}}$的优势是$\varepsilon $可忽略的。\par
		那么下面构造一个敌手$\mathcal{C}$，$\mathcal{C}$利用$\mathcal{A}$来攻击DL问题。
		则$\mathcal{C}$已知$g,{{\text{g}}^{x}}$，目标是计算x。\par
		设$a,b\in Z_{q}^{*}$，且$a\ne b$；\par
		\[\left\{ g,{{g}^{a}},{{g}^{b}} \right\}\leftarrow \mathcal{B}\]
		\[{{g}^{ab}}\leftarrow \mathcal{A}\]
		如果：${{g}^{ab}}={{g}^{ax}}$，则$x=b$;\\
		或${{g}^{ab}}={{g}^{bx}}$,则$x=a$；\\
		否则终止。
		此时敌手$\mathcal{C}$选中x的概率为$\dfrac{2}{q}$.\par
		又因为$\mathcal{A}$计算${{\text{g}}^{xy}}$的优势是$\varepsilon $，所以$\mathcal{C}$获胜的概率为$\dfrac{2\varepsilon }{q}$。
	}

	\begin{Exercise}
		设$\Pi '=(Enc',Dec')$是单钥加密方案，将9.2.2节中的加密方案修改如下：
		输入公开钥$(n,e)$和消息$m\in {{\left\{ 0,1 \right\}}^{\ell \left( k \right)}}$，选择一个随机数$r\leftarrow {}_{R}\mathbb{Z}_{n}^{*}$，输出密文 $({{r}^{e}}\bmod n,Enc_{k}^{'}(m))$。
		证明如果RSA问题是困难的，则修改后的加密方案是IND-CPA安全的公钥加密方案。		
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		设GenRSA是RSA加密方案的密钥生成算法，它的输入为$\kappa $，输出为模数$n$（为2个$\kappa $比特素数的乘积），整数$e,d$满足$ed\equiv 1\bmod \varphi (n)$。又设$H:{{\left\{ 0,1 \right\}}^{2\kappa }}\to {{\left\{ 0,1 \right\}}^{l(\kappa )}}$是一个哈希函数，其中$l(\kappa )$是一个任意的多项式。\par
		加密方案$\Pi '$如下：\\
		密钥产生过程：
		\[KeyGen(\kappa ):\]
		\[(n,e,d)\leftarrow GenRSA(\kappa )\]
		\[pk=(n,e),sk=(n,d)\]
		加密过程（其中$m\in {{\left\{ 0,1 \right\}}^{l(\kappa )}}$）
		\[{{E}_{PK}}(m)\]
		\[r\leftarrow {}_{R}\mathbb{Z}_{n}^{*}\]
		\[k=H(r)\]
		输出（${{r}^{e}}\bmod n,Ene_{k}^{'}(m)$）\par
		解密过程：
		\[{{D}_{sk}}({{C}_{1}},{{C}_{2}})\]
		\[r=C_{1}^{d}\bmod n\]
		输出\[Dec_{k}^{'}(m)\]。
		\par
		
		定理：设$H$是一个随机谕言机，如果与方案GenRSA相关的RSA问题是困难的，则方案$\Pi '$是IND-CPA安全的。
		即，设存在一个IND-CPA敌手$\mathcal{A}$以$\varepsilon $的优势攻破方案$\Pi '$，那么一定存在一个敌手$\mathcal{B}$至少以$Adv_{\mathcal{B}}^{RSA}(\kappa )\ge 2\varepsilon (\kappa )$的优势解决RSA问题。\par
		证明：$\Pi '$的IND-CPA游戏如下：
		\[EXP_{\mathcal{A}}^{\Pi '}(\kappa ):\]
		\[(n,e,d)\leftarrow GenRSA(\kappa );\]
		\[pk=(n,e),[sk=(n,d);\]
		\[H\leftarrow \left\{ H:{{\left\{ 0,1 \right\}}^{2\kappa }}\to {{\left\{ 0,1 \right\}}^{l(\kappa )}} \right\};\]
		\[k=H(r);\]
		\[({{m}_{0}},{{m}_{1}})\leftarrow {{\mathcal{A}}^{k}}(pk)\]，其中\[\left| {{m}_{0}} \right|=\left| {{m}_{1}} \right|=l(\kappa );\]
		\[\beta \leftarrow {}_{R}\left\{ 0,1 \right\},r\leftarrow {}_{R}\mathbb{Z}_{n}^{*};\]
		\[{{C}^{*}}=({{r}^{e}}\bmod n,Ene_{k}^{'}({{m}_{\beta }}))\]
		\[{{\beta }^{'}}\leftarrow {{\mathcal{A}}^{k}}(pk,{{C}^{*}})\]
		如果${{\beta }^{'}}=\beta $，则返回1，否则返回0.\par
		敌手的优势定义为安全参数$\kappa $的函数：
		\[Adv_{\mathcal{A}}^{\Pi '}(\kappa )=\left| \Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1 \right]-\frac{1}{2} \right|\]
		下面证明$\Pi '$方案可归约到RSA假设。\par
		敌手$\mathcal{B}$已知$(n,e,{{\hat{c}}_{1}})$，以$\mathcal{A}$（攻击$\Pi '$方案）作为子程序，进行以下过程，目标是计算$\hat{r}\equiv {{({{\hat{c}}_{1}})}^{\frac{1}{e}}}\bmod n$。\\
		1）	选取一个随机串$\hat{h}\leftarrow {}_{R}{{\left\{ 0,1 \right\}}^{l(\kappa )}}$，作为$H(r)$的猜测值，将公钥$(n,e)$发给$\mathcal{A}$。\\
		2）	H询问：$\mathcal{B}$建立一个表${{H}^{list}}$（初始为空），元素类型$({{x}_{i}},{{h}_{i}})$，$\mathcal{A}$在任何时候都能发出对${{H}^{list}}$的询问，$\mathcal{B}$做如下应答（设询问为x）\\
		--如果x已经在${{H}^{list}}$，则以$(x,h)$中的h应答；\\
		--如果${{x}^{e}}\equiv {{\hat{c}}_{1}}\bmod n$以$\hat{h}$应答，将$(x,\hat{h})$存入表中，并记下$\hat{r}=x$。\\
		--否则随机选择$h\leftarrow {}_{R}{{\left\{ 0,1 \right\}}^{l(\kappa )}}$以h应答，并将$(x,h)$存入表中。\\		
		3）挑战：$\mathcal{A}$输出两个挑战的消息${{m}_{0}}$和${{m}_{1}}$，$\mathcal{B}$随机选择$\beta \leftarrow {}_{R}\left\{ 0,1 \right\}$，
		并令$k=\hat{h},{{\hat{c}}_{2}}=Enc_{k}^{'}({{m}_{\beta }})$
		将$({{\hat{c}}_{1}},{{\hat{c}}_{2}})$给$\mathcal{A}$作为密文。\\
		4）在$\mathcal{A}$执行结束后（在输出其猜测$\beta '$之后），$\mathcal{B}$输出第2）步记下的$\hat{r}=x$。
		设$\mathcal{H}$表示事件：在模拟中$\mathcal{A}$发出$H(\hat{r})$询问，即$H(\hat{r})$出现在${{H}^{list}}$
		\par
		
		断言1：在以上模拟过程中，$\mathcal{B}$的模拟是完备的。\\
		证明:在以上模拟中，$\mathcal{A}$的视图与其在真实攻击中的视图是同分布的，这是因为\\
		1) $\mathcal{A}$的H询问中的每一个都是用随机值来回答的。而在$\mathcal{A}$对$\prod $的真实攻击中，$\mathcal{A}$得到的是H的函数值，由于假定H是随机谕言机，所以$\mathcal{A}$得到的H的函数值是均匀的。\\
		2）$Enc_{k}^{'}({{m}_{\beta }})$对$\mathcal{A}$来说，为$k$对${{m}_{\beta }}$做一次密加密。由$k$的随机性，$Enc_{k}^{'}({{m}_{\beta }})$对$\mathcal{A}$来说是随机的。
		所以两种视图不可区分。
		\par
		断言2：在上述模拟攻击中$\Pr \left[ \mathcal{H} \right]\ge 2\varepsilon $。\\
		证明：显然有$\Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1|\neg \mathcal{H} \right]=\frac{1}{2}$。\\
		又由$\mathcal{A}$在真实攻击中的定义，可知$\mathcal{A}$的优势大于等于$\varepsilon $，得$\mathcal{A}$在模拟攻击中的优势也为$\left| \Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1 \right]-\frac{1}{2} \right|\ge \varepsilon $。
		\[\Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1 \right]\]
		\[= \Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1|\neg \mathcal{H} \right]\Pr \left[ \neg \mathcal{H} \right]+\Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1|\mathcal{H} \right]\Pr \left[ \mathcal{H} \right]\]
		\[\le \Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1|\neg \mathcal{H} \right]\Pr \left[ \neg \mathcal{H} \right]+\Pr \left[ \mathcal{H} \right]\]
		\[=\frac{1}{2}\Pr \left[ \neg \mathcal{H} \right]+\Pr \left[ \mathcal{H} \right]\]
		\[=\frac{1}{2}(1-\Pr \left[ \mathcal{H} \right])+\Pr \left[ \mathcal{H} \right]\]
		\[=\frac{1}{2}+\frac{1}{2}\Pr \left[ \mathcal{H} \right]\]
		又知：
		\[\Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1 \right]\]
		\[\ge \Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1|\neg \mathcal{H} \right]\Pr \left[ \neg \mathcal{H} \right]\]
		\[=\frac{1}{2}(1-\Pr \left[ \mathcal{H} \right])\]
		\[=\frac{1}{2}-\frac{1}{2}\Pr \left[ \mathcal{H} \right]\]
		所以\[\varepsilon \le \left| \Pr \left[ Exp_{\mathcal{A}}^{\Pi '}(\kappa )=1 \right]-\frac{1}{2} \right|\le \frac{1}{2}\Pr \left[ \mathcal{H} \right]\]
		即模拟攻击中\[\Pr \left[ \mathcal{H} \right]\ge 2\varepsilon \]。
		由以上两个断言，在上述模拟过程中$\hat{r}$以至少$2\varepsilon $的概率出现在${{H}^{list}}$。若$\mathcal{H}$发生，则$\mathcal{B}$在第（2）步可找到x满足${{x}^{e}}\equiv {{\hat{c}}_{1}}\bmod n$，即$x\equiv \hat{r}\equiv {{({{\hat{c}}_{1}})}^{\frac{1}{e}}}\bmod n$。所以$\mathcal{B}$成功的概率与$\mathcal{H}$发生的概率相同。	
		
	}

	\begin{Exercise}
		Cramer-Shoup密码体制也使用哈希函数，其安全性证明为什么不是随机谕言机模型？
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		首先回顾随机谕言机的定义。在对方案进行安全性分析时，将其中的哈希函数视为随机谕言机。随机谕言机是一个魔盒 ，对用户（包括敌手）来说，魔盒内部的工作原理及状态都是未知的。用户能够与这个魔盒交互，方式是向魔盒输入一个比特串$x$，魔盒输出比特串$y$（对用户来说，$y$是均匀分布的）。这一过程称为用户向随机谕言机询问。由于这种哈希函数工作原理和内部状态是未知的，因此不能用通常的公开哈希函数。在安全性的归约证明中，敌手$\mathcal{A}$需要哈希函数值时，只能由敌手$\mathcal{B}$为他产生。之所以以这种方式使用哈希函数，是因为$\mathcal{B}$要把欲攻击的困难问题嵌入到哈希函数值中。这种安全性称为随机谕言机模型下的。如果不把哈希函数当作随机谕言机，则安全性称为标准模型下的。\par
		而Gramer-Shoup的证明过程无需把困难问题嵌入到哈希函数中，所以它是标准模型下的证明过程。 
		
	}

	\begin{Exercise}
		（1）在Paillier方案1中，设，$n=5\times 7，g=13$，在对$m=23$加密时，取$r=19$，计算密文，并验证解密过程。\par
		（2）在Paillier方案2中，设$n=5\times 7，g=13$，计算$m=1178$的密文，并验证解密过程。	
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		因为在Paillier方案1中，
		加密算法为：\[CT={{g}^{m}}{{r}^{n}}\bmod {{n}^{2}}\]
		解密算法为：\[\frac{L(C{{T}^{\lambda }}\bmod {{n}^{2}})}{L({{g}^{\lambda }}\bmod {{n}^{2}})}\bmod n\equiv M\]
		
		所以当\[n=5\times 7\]，\[g=13\]，\[m=23\]，\[r=19\]时，其密文为：
		\[{{g}^{m}}{{r}^{n}}\bmod {{n}^{2}}={{13}^{23}}\times {{19}^{35}}\bmod {{35}^{2}}=[({{13}^{23}}\bmod {{35}^{2}})\times ({{19}^{35}}\bmod {{35}^{2}})]\bmod {{35}^{2}}\]
		\[=(342\times 734)\bmod {{35}^{2}}\]\[=1128\]
		解密过程：
		
		解密为：\[M\equiv \frac{L(C{{T}^{\lambda }}\bmod {{n}^{2}})}{L({{g}^{\lambda }}\bmod {{n}^{2}})}\bmod n=\frac{\lambda {{\left[ \left[ CT \right] \right]}_{1+n}}}{\lambda {{\left[ \left[ g \right] \right]}_{1+n}}}=\frac{{{\left[ \left[ CT \right] \right]}_{1+n}}}{{{\left[ \left[ g \right] \right]}_{1+n}}}\equiv {{\left[ \left[ CT \right] \right]}_{g}}\bmod n\]
		即\[{{\left[ \left[ 1128 \right] \right]}_{13}}\bmod 35\]
		
		
	}

\chapter{网络安全}
	\begin{Exercise}
		下面是X.509三向认证的最初版本\\
		$A\to BA\left\{ {{t}_{A}},{{r}_{A}},B \right\}$\\
		$B\to A:B\left\{ t{}_{B},{{r}_{B}},A,{{r}_{A}} \right\}$\\
		$A\to B:A\left\{ {{r}_{B}} \right\}$\\
		假定协议不使用时间戳，可在其中将所有时间戳设置为0，则攻击者C如果截获A、B之前执行协议时的消息，就可假冒A和B，以使A(B)相信通信的对方是B(A).请提出一种不使用时间戳的、防中间人欺骗的简单方法。		
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		方案如下：\\
		$A\to BA\left\{ {{t}_{A}},{{r}_{A}},B,fla{{g}_{A}} \right\}$\\
		$B\to A:B\left\{ t{}_{B},{{r}_{B}},A,{{r}_{A}},fla{{g}_{B}} \right\}$\\
		$A\to B:A\left\{ {{r}_{B}},fla{{g}_{A}} \right\}$\\
		需要交互的用户A和B提前设置一个只有双方知道的口令password。其中的$flag=password\oplus {{r}_{{}}}$。
		当接收方收到发送方的消息之后进行：$flag\oplus {{r}_{{}}}$，若得的值为之前商定好的password值，则说明发送方的可信的。上述过程即是不使用时间戳的、防止中间人欺骗的一种简单方法。
		
	}

	\begin{Exercise}
		在PGP中，若用户有N个公开钥，则密钥ID至少有两个重复的概率有多大？
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		在PGP中，用公开钥中64个最低有效位表示该密钥的ID，即公开钥$P{{K}_{A}}$的ID是$P{{K}_{A}}\bmod {{2}^{64}}$。由于64位已经足够长，所以不同密钥ID重复的概率非常小。
		密钥ID 的可能取值共有${{2}^{^{64}}}$种，则当用户有N个公开钥时，ID取值共有${{\left( {{2}^{64}} \right)}^{N}}$种，密钥ID至少有两个重复的概率为$1-\frac{{{2}^{64}}!}{{{\left( {{2}^{64}} \right)}^{N}}*\left( {{2}^{64}}-N \right)!}$。
		
	}

	\begin{Exercise}
		在PGP中，先对消息签名再对签名加密，请详细说明这一顺序为什么优于先加密再对加密结果签名。
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		将签字与明文消息在一起存储比与密文消息在一起存储会带来很多方便，同时也给第三方对签字的验证带来方便。如果先加密消息再对消息签字，签字将和密文消息放在一起，这不利于存储消息，也不利于第三方验证签字。另外，加密之前需要压缩，对不压缩的消息签字，可便于以后对签字的验证。如果对压缩后的消息签字，则为了以后对签字的验证，需存储压缩后的消息 或在验证签字时对消息重做压缩。并且，zip压缩算法是不确定性的，该算法在不同的实现中会由于在运行速度和压缩率之间产生不同的折中，产生出不同的压缩结果。
	}

	\begin{Exercise}
		在PGP的消息格式中，消息摘要的前两个8比特位组以明文形式传输。\\
		（1）说明这种形式对哈希函数的安全性有多大程度的影响。\\
		（2）接收方用消息摘要的前两个8比特位组，确定自己在验证发送方的数字签名时是否正确地使用了发送方的公开钥，其可信程度有多大？
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		(1)首先，哈希函数满足如下几个性质:\\
		a.输入为任意长度，输出为固定长度，便于计算与实现。\\
		b.哈希函数具有单向性。\\
		c.哈希函数具有抗碰撞性。在PGP中，消息摘要有SHA对签名的时间戳链接上本身后求得的160比特哈希函数输出结果。公开的消息摘要的前两个8比特位数组（哈希结果的前两个8比特位数组内容），对哈希函数的安全性没有影响。
		\par
		
		(2)消息摘要是对签名的时间戳链接上消息本身后求得的160比特函数输出，然后再由发送方使用秘密要进行签名所得。接收方验证签名时，即为使用对应发送方公钥进行签名验证，其可信程度与签名算法的安全性相关，如果使用的签名算法具有不可伪造性，那么这种验证方式就是可信安全的。
	}

	\begin{Exercise}
		在表10-2中，公钥环中的每一项都有一个拥有者可信字段，用以表示这一公钥的属主(即拥有这一公钥的用户)的可信程度。这一字段能否充分表达PGP对这一公钥的信任？如果不能，则如何实现PGP对这一公钥的信任？
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		PGP是一个网络，每个人在信任链中都作为到另一个人的介绍人。PGP把密钥签名作为一种介绍形式。当某个人签署了一个密钥时，他就成为那个密钥的潜在介绍人。例如，假设Alice签署了Bob的密钥，而Bob签署了Charlie的密钥。
		\par
		Alice现在就有了一个到Chrlie的证明路径。Alice现在有一种方式知道Charlie的密钥确实是Charlie的，因为上面有Bob的签名，而且Alice知道Bob的密钥确实是Bob的。这是一种在密钥中提供可传递的信任。
		\par
		这个设计中有一个明显的问题。如果有人作为介绍人，但是并不真正知道他所介绍的人会怎么样呢？例如，如果Bob非常粗心，虽然签署了Doug的密钥，却宣称是Charlie的。不仅Bob认为这处密钥属于Charlie（尽管是Doug但却宣称它属于Charlie），而且因为对受托性没有一种度量，Alice也会相信。
		\par
		这就是PGP信任网中所发生的。通过信任网（Web of Trust），用户定义了对一个密钥的信任量，作为介绍人。在前面的例子中，Alice给予Bob的密钥尽可能多的信任，而且如果他相信Bob正确地签署了其他人的密钥，他也会相信这个密钥。如果Alice知道Bob对于密钥验证很松懈，他就不会再信任Bob作介绍人了。其结果是，Alice不会再相信Bob为Doug签署的但宣称为Charlie的密钥。
		\par
		当然，信任网也不是绝对安全。如果有人被欺骗签署了一个错误的密钥，它就会使得其他人错误地相信它。PGP信任网被认为是一个声誉系统，受到尊敬的人给出好的签名，其他人则给出不好的签名。当存在错误的声誉时，系统就可能失效。
		\par
		综上所述，我们可知，PGP的信任字段并不能充分表达用户对这一公钥的信任。用户要根据证书链以及信誉系统来计算对特定公钥的信任程度。
		\par
		如果使用用户充分信任的第三方机构或个人为特定公钥签字，可以实现用户对这一公钥的充分信任。
		
	}

	\begin{Exercise}
		
		\cite{yang-mcry}
	\end{Exercise}
	\jd{
		
	}
%----------------------
%      参考文献
%----------------------

\bibliographystyle{plain} 
\bibliography{../crybook/chapters/myreference}
	   

\end{document}